Question

Provide the dynamic-programming recurrence for a function that is used to solve 0-1 Knapsack. Clearly define what the function is computing.

Answer 1

DYNAMIC PROGRAMMING RECURRENCE FOR 0-1 KNAPSACK PROBLEM

• Let f(i,y) be the profit value of the optimal solution to the knapsack instance defined by the state (i,y). Items i through n are available. Available capacity is y.
• For the time being assume that we wish to determine only the value of the best solution. Later we will worry about determining the x_is that yield this maximum value.
• Under this assumption, our task is to determine f(1,c).
• f(n,y) is the value of the optimal solution to the knapsack instance defined by the state (n,y). Only item n is available. Available capacity is y.
• If w_n <= y, f(n,y) = p_n .
• If w_n > y, f(n,y) = 0.
• Suppose that i < n.
• f(i,y) is the value of the optimal solution to the knapsack instance defined by the state (i,y). Items i through n are available. Available capacity is y.
• Suppose that in the optimal solution for the state (i,y), the first decision is to set x_i= 0.
• From the principle of optimality (we have shown that this principle holds for the knapsack problem), it follows that f(i,y) = f(i+1,y).
• The only other possibility for the first decision is x_i= 1.
• The case x_i= 1 can arise only when y >= w_i.
• From the principle of optimality, it follows that f(i,y) = f(i+1,y-wi ) + p_i.
• Combining the two cases, we get
  • f(i,y) = f(i+1,y) whenever y < w_i.
  • f(i,y) = max{f(i+1,y), f(i+1,y-w_i ) + p_i }, y >= w_i

The function for knapsack using dynamic programming:

static int knapSack(int W, int wt[], int val[], int n) 
    { 
        int i, w; 
        int K[][] = new int[n + 1][W + 1]; 
  
        // 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]; 
            } 
        } 
  
        return K[n][W]; 
    } 

Explanation of the above function:

Let weight elements = {1, 2, 3}
Let weight values = {10, 15, 40}
Capacity=6

   0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0
 
Explanation:

​
Let weight elements = {1, 2, 3}
Let weight values = {10, 15, 40}
Capacity=6

   0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0

Explanation:
For filling 'weight = 2' we come 
across 'j = 3' in which 
we take maximum of 
(10, 15 + DP[1][3-2]) = 25   
  |        |
'2'       '2 filled'
not filled  


   0   1   2   3   4   5   6

0  0   0   0   0   0   0   0

1  0  10  10  10  10  10  10

2  0  10  15  25  25  25  25

3  0  10  15  40  50  55  65

Explanation:
For filling 'weight=3', 
we come across 'j=4' in which 
we take maximum of (25, 40 + DP[2][4-3]) 
= 50

For filling 'weight=3' 
we come across 'j=5' in which 
we take maximum of (25, 40 + DP[2][5-3])
= 55

For filling 'weight=3' 
we come across 'j=6' in which 
we take maximum of (25, 40 + DP[2][6-3])
= 65