The Knapsack Problem

1.  Problem Denition

    --  Input: n items. Each has a:

        a) Value vi (nonnegative)

        b) Size wi (nonnegative and integral)

        Capacity W (a nonnegative integer)

    --  Output: A subset S of {1, 2, ... , n} that maximizes sum(i in S) {vi} subject to Sum(i in S) {wi} <= W.

 

2.  A Dynamic Programming Algorithm

    --  Formulate recurrence [optimal solution as function of solutions to "smaller subproblems"] based on a structure of an optimal solution.

    --  Let S = a max-value solution to an instance of knapsack.

    --  Case 1: Supose item n not in S. ==> S must be optimal with the first n-1 items (same capacity W) because 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 n in S. Then S - {n} is an optimal solution with respect to the 1st n - 1 items and capacity W - wn. Because If S* has higher value than S -{n} and its total size <= W - wn,

then S* U {n} has size <= W and value more than S [contradiction]

 

3.  The Subproblems

    --  Let V(i , x) = value of the best solution that:

       (1) uses only the first i items

       (2) has total size <= x

    --  For i in {1, 2, ... , n} and only x,

        V(i , x) = max {V(i-1 , x) (case 1, item i excluded), vi + V(i-1 , x-wi) (case 2, item i included) }

    --  Edge case: If wi > x, must have V(i , x) = V(i-1 , x)

    --  Identify the subproblems:

        a) All possible prefixes of items {1, 2, ... , i} , i in { 0, 1, 2, ..., n}

        b) All possible (integral) residual capacities x in {0, 1, 2, ... , W}

    --  Use recurrence to systematically solve all problems:

        a) Let A = 2-D array

        b) Initialize A[0 , x] = 0 for x = 0, 1, ... , W

        c) For i = 1, 2, ... , n

                For x = 0, 1, ... , W

                    A[i , x] := max { A[i - 1 , x] , A[i - 1; x - wi ] + vi } (Ignore second case if wi > x)

        d) Return A[n,W]

    --  Running Time: O(nW)

 

4.  Example :