CODEWITHSUNDEEP
algorithmdynamic-programmingpseudocodeknapsack-problem
LearningToCode
LearningToCode

Reputation: 651

Algorithm for Knapsack with repetition

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.

Upvotes: 5

Views: 8586

Answers (2)

MoeChen
MoeChen

Reputation: 789

Based on Algorithms DVP, the solution to Knapsack with repetition is like below:

K(0)=0
for w=1 to W:
    K(w) = max{K(w - w_i) + v_i, w_i < w}
return K(W)

Here, W is the capacity; w_i is the weight of item i; v_i is the value of item i; K(w) is the max value achievable with knapsack of capacity w.

Your solution seems like 0-1 Knapsack though.

Upvotes: 0

amit
amit

Reputation: 178521

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)

Upvotes: 5

Related Questions