Editing Knapsack problem (section)

=== Dynamic programming in-advance algorithm ===
The '''unbounded knapsack problem''' ('''UKP''') places no restriction on the number of copies of each kind of item. Besides, here we assume that <math>x_i > 0</math>
: <math>m[w']= \max \left( \sum_{i=1}^n v_i x_i \right)</math>
: subject to <math>\sum_{i=1}^n w_i x_i \leq w'</math> and <math>x_i > 0</math>

Observe that <math>m[w]</math> has the following properties:

1. <math>m[0]=0\,\!</math> (the sum of zero items, i.e., the summation of the empty set).

2. <math>m[w]=\max (v_1+m[w-w_1],v_2+m[w-w_2],...,v_n+m[w-w_n])</math>
, <math>w_i \leq w</math>, where <math>v_i</math> is the value of the <math>i</math>-th kind of item.

The second property needs to be explained in detail. During the process of the running of this method, how do we get the weight <math>w</math>? There are only <math>i</math> ways and the previous weights are <math>w-w_1, w-w_2,..., w-w_i</math> where there are total <math>i</math> kinds of different item (by saying different, we mean that the weight and the value are not completely the same). If we know each value of these <math>i</math> items and the related maximum value previously, we just compare them to each other and get the maximum value ultimately and we are done.

Here the maximum of the empty set is taken to be zero. Tabulating the results from <math>m[0]</math> up through <math>m[W]</math> gives the solution. Since the calculation of each <math>m[w]</math> involves examining at most <math>n</math> items, and there are at most <math>W</math> values of <math>m[w]</math> to calculate, the running time of the dynamic programming solution is [[Big O notation|<math>O(nW)</math>]]. Dividing <math>w_1,\,w_2,\,\ldots,\,w_n,\,W</math> by their [[greatest common divisor]] is a way to improve the running time.

Even if [[P versus NP problem|P≠NP]], the <math>O(nW)</math> complexity does not contradict the fact that the knapsack problem is [[NP-complete]], since <math>W</math>, unlike <math>n</math>, is not polynomial in the length of the input to the problem. The length of the <math>W</math> input to the problem is proportional to the number of bits in <math>W</math>, <math>\log W</math>, not to <math>W</math> itself. However, since this runtime is [[pseudopolynomial]], this makes the (decision version of the) knapsack problem a [[weak NP-completeness|weakly NP-complete problem]].

==== 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>