CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Aniket
Aniket

Reputation: 27

Knapsack Algorithm: Why we use wt[i-1] instead of wt[i]

Considering the following part of an implementation of Knapsack algorithm:

 // Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
    for (w = 0; w <= W; w++)
    {
        if (i == 0 || w == 0)
            K[i][w] = 0;
        else if (wt[i - 1] <= w)
            K[i][w]
                    = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
        else
            K[i][w] = K[i - 1][w];
    }
}

I have a basic doubt why we use wt[i-1] while we are checking the ith element?

Upvotes: 0

Views: 125

Answers (2)

Orhan Tuncer
Orhan Tuncer

Reputation: 154

That gives us the best value we can get if we do not select item i. Consider items (value,volume); (2,1), (3,2), (4,5) and a bag of volume 5.

When we are dealing with the third item we can have a value of 4. But if we do not take it, we can have our previous max value which is 5. Check this video.

Upvotes: 1

Sorin
Sorin

Reputation: 11968

Your first for loop runs i=0; i<=n; i++ this means it will run n+1 iterations, while you have only n objects. This is OK, because i=0 is special cased to assign K[i][w] = 0 so basically this will initialize the first row with 0s. Now that i=0 has a special meaning, the array is shifted by 1 (so i=1 refers to the first object with weight wt[0], and so on).

You don't really need this kind of tricks, but they are common for dynamic programming. If you don't want to add an extra column for 0 you can omit it, but then you need to add a bunch of checks to make sure you don't try to access memory outside of the allocated area, which makes it a bit harder to test since you have two paths for your logic.

Upvotes: 0

Related Questions