Вариант рюкзака

Question

Как и в оригинальной задаче, мне даются некоторые предметы (с весом и стоимостью) и должны заполнять рюкзак, чтобы получить максимальную общую стоимость. Однако в этой версии алгоритма мне предоставляется неограниченное количество копий каждого элемента. Не могли бы вы предложить несколько идей/псевдокодов?

Answer 1

Это называется проблемой неограниченного рюкзака, и есть много ссылок. Некоторые могут включать в себя:

• https://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem
• http://www.csegeek.com/csegeek/view/tutorials/algorithms/dynamic_prog/dp_part7.php
• http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack2.html