Dynamic Programming

Question

int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be
// put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
    // Base Case
    if (n == 0 || W == 0)
        return 0;

    // If weight of the nth item is more than
    // Knapsack capacity W, then this item cannot
    // be included in the optimal solution
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);

    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max(
            val[n - 1]
                + knapSack(W - wt[n - 1],
                        wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}

// Driver program to test above function
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}
 

Hello Folks, can you please help me to understand the below snippet of code?

“return max(
            val[n - 1]
                + knapSack(W - wt[n - 1],
                        wt, val, n - 1),
            knapSack(W, wt, val, n - 1));

}” This statement implies that the max value return by the two different recursive problems right?

Answer 1

The $knapSack(W, wt[ ], val[ ], n)$ returns maximum value that can be put into $sack$ of maximum weight capacity of $W$ from $n$ items.

The code snippet that you mentioned only runs when $wt[n] \le W$ ie you get to choose whether to take $n^{th}$ item or not.

Now, if you choose to take $n^{th}$ item then the value that you'll get is $val[n] + knapSack(W-wt[n], wt[ ], val[ ], n-1)$ ie if you choose to take $n^{th}$ item your sack will have value of this $n^{th}$ item plus whatever value you get from remaining $n-1$ items.

Now, if you choose not to take $n^{th}$ item then the value that you'll get is $knapSack(W, wt[ ], val[ ], n-1)$ ie if you choose not to take $n^{th}$ item your sack will have whatever value you get from remaining $n-1$ items.

At last, you return whichever choice gives you maximum value as that was the original goal.

Comments

For the sake of reference, you can apply the brute force method by taking sample weight and profit. Here we will be using a 2-D array to store a maximum value keeping in mind that value<=weight.