Algorithm for Knapsack with repetition

Question

I am trying to devise a pseudo-code for Knapsack algorithms, where a single item can be selected multiple times. The classical algorithm is

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i-1, w-wi))

In order to meet the requirements, I am modifying it to

k=1;
max = maximum(OPT(i-1, w))
while(OPT(i-1, w - k*wi) > 0) {
  maximum = max(maximum, k*vi + OPT(i-1, w - k*wi))
  k++
}
OPT(i, w) = maximum

Does this seem to be an appropriate solution? Or any better solution exists? Please let me know if any additional information is required. Rest all remains the same, vi denotes the value of ith element and wi denotes the weight of ith element.

Answer 1

If you want to be able to chose multiple items, all you have to do is to change the recursion when selecting an element:

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i, w-wi))
                     ^                   ^
          removed the element      not removing the element

The idea is, you allow readding it on next iteration. You add an element as much as you want, and you stop adding it when you "chose" to use the first condition in the stop recursive formula.

The recursion will still not be infinite because you must stop once w<0.

Time complexity does not change - O(nW)