CODEWITHSUNDEEP
javaalgorithmdynamic-programmingknapsack-problem
Cratylus
Cratylus

Reputation: 54074

Trying to figure out the classic Knapsack recurrence

I am reading about the Knapsack Problem (unbounded) which is, as I understand a classic in DP.
Although I think I understand the solution as I read it, I am not clear how I can translate it to actual code.
For example in the following recurrence "formula":

M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1

I am not sure how I can translate this to code, since it is not clear to me if the inner MAX should be there or it should just be instead:
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1

Any help to figure out the formula and to code it?

Upvotes: 3

Views: 4200

Answers (1)

mamdouh alramadan
mamdouh alramadan

Reputation: 8528

you can code it like this:

for w = 0 to W   //W is the maximum capacity
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
    if wi <= w // item i can be part of the solution
        if  bi + V[i-1,w-wi] > V[i-1,w]
            V[i,w] = bi + V[i-1,w- wi]
        else
            V[i,w] = V[i-1,w]
    else V[i,w] = V[i-1,w]  // wi > w

enter image description here

this means the following:

It means, that the best subset of Sk that has total weight w is:

1) the best subset of Sk-1 that has total weight > w, or

2) the best subset of Sk-1 that has total weight > w-wk plus the item k

The best subset of Sk that has the total weight > w, either contains item k or not.

First case: wk>w. Item k can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.

Second case: wk <= w. Then the item k can be in the solution, and we choose the case with greater value.

Upvotes: 8

Related Questions