Given a knapsack (bag or container) with:

• M – capacity of the knapsack
• n – number of objects
• w – an array consisting of the weights w₁, w₂, w₃, …, w_n
• P – an array consisting of the profits P₁, P₂, P₃, …, P_n
• x – an array consisting of 0 or 1: x_i = 0 means the i^th object has not been selected, and x_i = 1 means it has been selected.

The main objective is to place the objects into the knapsack so that the maximum profit is obtained:

Dynamic programming for 0/1 knapsack

Let i represent the i^th object in question, to be selected or not, with weight w_i and profit P_i, and let j be the remaining capacity, the aim being to get the maximum profit. $V[i,j]$ is the profit obtained by considering all i objects with capacity j.

Case 1

If there are no objects (i = 0) or the capacity of the knapsack itself is zero (j = 0), the profit is 0:

Case 2

(the weight of the i^th object is greater than the remaining capacity j). In this case the object is not selected, because it cannot fit into the knapsack.

Case 3

w_i is less than or equal to j, so there are two alternatives:

• Reject the i^th object ⇒ profit $V[i,j]=V[i-1,j]$
• Select the i^th object ⇒ profit $V[i,j]=V[i-1,j-w_i]+P_i$

Whichever yields the maximum profit is selected:

Complete recurrence

$V[N,M]$ gives the optimal profit obtained.

Example

Solution: N = 4, w₁ = 2, w₂ = 1, w₃ = 3, w₄ = 2, and P₁ = 12, P₂ = 10, P₃ = 20, P₄ = 15.

The solution matrix consists of N + 1 rows and M + 1 columns.

Step 1

In the bottom-up approach, start from the initial solutions i = 0 or j = 0. For i = 0 there are no objects, and for j = 0 the capacity is zero, so these entries are 0 (the profit table).

Step 2: i = 1, w_i = 2, P_i = 12

Check whether object 1 can be selected or not.

Step 3: i = 2, w_i = 1, P_i = 10

Step 4: i = 3, w_i = 3, P_i = 20

Step 5: i = 4, w_i = 2, P_i = 15

The completed profit table

$V[N,M]=V[4,5]=37$, the optimal solution (the highlighted cells are the ones visited when finding the objects selected).

Objects selected

Initially $(x_1,x_2,x_3,x_4)=(0,0,0,0)$, which indicates that no objects are selected. The remaining capacity is j = 5.

Check: profit = 12 + 10 + 15 = 37, and weight = 2 + 1 + 2 = 5 ≤ M.

Algorithm KNAPSACK(n, m, w, P, V)

ALGORITHM KNAPSACK(n, m, w, P, V)
/* To find the optimal solution for the knapsack problem using
   dynamic programming.
   n - number of objects
   m - capacity of the knapsack
   w - weights of all the objects
   P - profits of all the objects
   Output: V - optimal solution */
for i ← 0 to n do
    for j ← 0 to m do
        if (i = 0 or j = 0)
            V[i,j] = 0
        else if (w[i] > j)
            V[i,j] = V[i-1,j]
        else
            V[i,j] = max(V[i-1,j], V[i-1,j-w[i]] + P[i])
        end if
    end for
end for
return