I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand right now so I am not interested in any particular code. For example here is how I solve the 0-1 problem. How do I need to modify this if I am given an infinity amount of copies of each item?
Edit: I am aware there is a second solution to the problem containing items 1,2, and 3 with the same total value.
Best How To :
One possibility would be to provide a suitable number of multiplicities of the items. For item
i, there can be at most
m_i := K / w_i
choices of that item, where
K denotes the knapsack capacity and
w_i denotes the weight of the
i-th item. Furthermore, for each weight value which occurs in the instance, there is at most one item type necessary, namely the one with maximum profit with respect to the weight.
Equivalently, one could modify the evaluation of the dynamic program to reflect the different number of items to be taken, instead of just distinguishing between a choice of