in Algorithms edited by
185 views
0 votes
0 votes
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?
in Algorithms edited by
185 views

1 Answer

1 vote
1 vote
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.

1 comment

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.

0
0