Editing Knapsack problem (section)

==== 0-1 knapsack problem ====
[[File:Knapsack problem dynamic programming.gif|alt=A demonstration of the dynamic programming approach.|thumb|A demonstration of the dynamic programming approach.]]
A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time. Assume <math>w_1,\,w_2,\,\ldots,\,w_n,\, W</math> are strictly positive integers. Define <math>m[i,w]</math> to be the maximum value that can be attained with weight less than or equal to <math>w</math> using items up to <math>i</math> (first <math>i</math> items).

We can define <math>m[i,w]</math> recursively as follows: '''(Definition A)'''
* <math>m[0,\,w]=0</math>
* <math>m[i,\,w]=m[i-1,\,w]</math> if <math>w_i > w\,\!</math> (the new item is more than the current weight limit)
*<math>m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)</math> if <math>w_i \leqslant w</math>.

The solution can then be found by calculating <math>m[n,W]</math>. To do this efficiently, we can use a table to store previous computations.

The following is pseudocode for the dynamic program:

<syntaxhighlight lang="c" line>
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 1 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

</syntaxhighlight>

This solution will therefore run in <math>O(nW)</math> time and <math>O(nW)</math> space. 
(If we only need the value m[n,W], we can modify the code so that the amount of memory required is O(W) which stores the recent two lines of the array "m".)

However, if we take it a step or two further, we should know that the method will run in the time between <math>O(nW)</math> and <math>O(2^n)</math>. From '''Definition A''', we know that there is no need to compute all the weights when the number of items and the items themselves that we chose are fixed. That is to say, the program above computes more than necessary because the weight changes from 0 to W often. From this perspective, we can program this method so that it runs recursively.

<syntaxhighlight lang="c" line="1">
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

Define value[n, W]

Initialize all value[i, j] = -1

Define m:=(i,j)         // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
{
    if i == 0 or j <= 0 then:
        value[i, j] = 0
        return

    if (value[i-1, j] == -1) then:     // m[i-1, j] has not been calculated, we have to call function m
        m(i-1, j)

    if w[i] > j then:                      // item cannot fit in the bag
        value[i, j] = value[i-1, j]
    else: 
        if (value[i-1, j-w[i]] == -1) then:     // m[i-1,j-w[i]] has not been calculated, we have to call function m
            m(i-1, j-w[i])
        value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
}

Run m(n, W)
</syntaxhighlight>

For example, there are 10 different items and the weight limit is 67. So,
<math display=block>\begin{align}
&w[  1]= 23 ,w[  2]= 26,w[  3]= 20,w[  4]= 18,w[  5]= 32,w[  6]= 27,w[  7]= 29,w[  8]= 26,w[  9]= 30,w[ 10]= 27 \\
&v[  1]=505 ,v[  2]=352,v[  3]=458,v[  4]=220,v[  5]=354,v[  6]=414,v[  7]=498,v[  8]=545,v[  9]=473,v[ 10]=543 \\
\end{align}</math>
If you use above method to compute for <math>m(10,67)</math>, you will get this, excluding calls that produce <math>m(i,j) = 0</math>:
<math display=block>\begin{align}
&m(10, 67) = 1270\\
&m(9, 67) = 1270, m(9, 40) = 678\\
&m(8, 67) = 1270, m(8, 40) = 678, m(8, 37) = 545\\
&m(7, 67) = 1183, m(7, 41) = 725, m(7, 40) = 678, m(7, 37) = 505\\
&m(6, 67) = 1183, m(6, 41) = 725, m(6, 40) = 678, m(6, 38) = 678, m(6, 37) = 505\\
&m(5, 67) = 1183, m(5, 41) = 725, m(5, 40) = 678, m(5, 38) = 678, m(5, 37) = 505\\
&m(4, 67) = 1183, m(4, 41) = 725, m(4, 40) = 678, m(4, 38) = 678, m(4, 37) = 505, m(4, 35) = 505\\
&m(3, 67) = 963, m(3, 49) = 963, m(3, 41) = 505, m(3, 40) = 505, m(3, 38) = 505, m(3, 37) = 505, m(3, 35) = 505, m(3, 23) = 505, m(3, 22) = 458, m(3, 20) = 458\\
&m(2, 67) = 857, m(2, 49) = 857, m(2, 47) = 505, m(2, 41) = 505, m(2, 40) = 505, m(2, 38) = 505, m(2, 37) = 505, m(2, 35) = 505, m(2, 29) = 505, m(2, 23) = 505\\
&m(1, 67) = 505, m(1, 49) = 505, m(1, 47) = 505, m(1, 41) = 505, m(1, 40) = 505, m(1, 38) = 505, m(1, 37) = 505, m(1, 35) = 505, m(1, 29) = 505, m(1, 23) = 505\\
\end{align}</math>

Besides, we can break the recursion and convert it into a tree. Then we can cut some leaves and use [[parallel computing]] to expedite the running of this method.

To find the actual subset of items, rather than just their total value, we can run this after running the function above:<syntaxhighlight lang="c" line="1">
/**
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
 */
function knapsack(i: int, j: int): Set<int> {
    if i == 0 then:
        return {}
    if m[i, j] > m[i-1, j] then:
        return {i} ∪ knapsack(i-1, j-w[i])
    else:
        return knapsack(i-1, j)
}

knapsack(n, W)
</syntaxhighlight>