knapsack problem

• n items. Each has attibutes:
  • value $v_i$(nonnegative)
  • size $w_i$(nonnegative and integral)
• and the capacity W (a nonnegative integer)

• A subset $S subset {1, 2,…, n}$ that maximizes $sum_{iin S} v_i $ subject to $sum_{iin S} w_i leq W$

• Let $S$ = a max-value solution to an instance of knapsack
  • case 1: suppose item $nnotin S$ => $S$ must be optimal with the first $n-1$ items (If $S^*$ were better than $S$ with respect to 1st $n − 1$ items, then this equally true w.r.t. all $n$ items - contradiction)
  • case 2: suppose item $nin S$ => $S - {n}$ must be an optimal solution with respect to the 1st $n-1$ items and capacity $W-w_n$ (If $S^∗$ has higher value than $S − {n}$ && $total Size ≤ W − w_n$ ,then $S^∗∪ {n}$ has $size ≤ W$ and value more than $S$ - contradiction)

• All possible prefixes of items ${1, 2, . . . , i}$
• All possible (integral) residual capacities $x ∈ {0, 1, 2, . . . , W }$

Step 3: Use recurrence from Step 1 to systematically solve all problems.

1
2
3
4
5
6

Let A = 2-D array 
Initialize A[0,x] = 0 for x = 0, 1,...,W 	
For i = 1, 2, . . . , n 
    For x = 0, 1, . . . , W		
        A[i, x] := max{ A[i − 1, x] , A[i − 1, x − w i ] + vi }
Return A[n, W ]

​

​