Easy Steps To Master 0–1 Knapsack Problem

8 min readApr 5, 2022

What is the knapsack problem?

Knapsack problem is a problem in which we have certain weights given to us along with their values/cost and the total capacity of the knapsack. Our goal is to pack the knapsack in such a way that we get the maximum total value/cost, keeping in mind that the total weight we can add is fixed.

There are 2 versions of knapsack problem, here we will be discussing the 0–1 knapsack problem.

In the 0–1 knapsack problem, the items are indivisible we can either pick the item or drop it. This problem is solved using Dynamic Programming.

0–1 Knapsack Problem

Given: A knapsack with maximum capacity W and n items that need to be added to the knapsack.

Each item i has some weight wᵢ and cost cᵢ.

To find: How to pack the knapsack to attain the maximum total value of packed items?

Solving using brute force approach:

As there are n items, therefore there are 2ⁿ possible combinations of items and we need to go through all the combinations to find the best fit, so the time complexity will be O(2ⁿ).

Solving using Dynamic Programming:

The recursive formula is:

First case: wᵢ > W

Item i cannot be added to the knapsack as the maximum weight of the knapsack is W.

Second case: wᵢ ≤ W

Item i can be added to the knapsack and we will choose the case with more cost/benefit value.

0–1 Knapsack Algorithm

for w = 0 to W                                -----O(W)
  C[0,w] = 0 
for i = 1 to n 
  C[i,0] = 0                                  
for i = 1 to n                               -----Repeat n times
 for w = 0 to W                              -----O(w)
  if wᵢ<= w // item i can be added to knapsack
    if cᵢ + C[i-1, w-wᵢ] > C[i-1, w]
            C[i,w] = cᵢ + C[i-1, w-wᵢ]
    else
            C[i,w] = C[i-1,w]
  else
    C[i,w] = C[i-1,w]  // wᵢ > W

Time complexity = O(n*W)

Example:

n = 4 (no. of items)
W = 5 (max capacity of knapsack)
Items (weight, benefit) = (2,3) , (3,4) , (4,5) , (5,6)

Step 1

As no item can be added so the first row will be filled with 0.

Step 2

The first column will be filled with 0 as the maximum capacity of the bag is 0 and therefore no item can be added.

Step 3

C[1,1]: We can only use the first item i.e (2,3) and as the weight of the item is 2 and the maximum capacity of the subproblem is 1, the item cannot be added and the first condition of the recursive formula will be used.

C[1,1] = C[1,0]

i=1; 
cᵢ = 3; 
wᵢ = 2; 
w = 1; 
w-wᵢ = -1;

Step 4

C[1,2]: We can only use the first item i.e (2,3) and as the weight of the item is 2 and the maximum capacity of the subproblem is 2, the item can be added to the knapsack so the second condition of the recursive formula will be used. The maximum of the previous condition and the current value will be taken. And hence 3 will be filled in the matrix as the value of the first item is 3.

i=1; 
cᵢ = 3; 
wᵢ = 2; 
w = 2; 
w-wᵢ = 0;

Step 5

C[1,3]: We can only use the first item i.e (2,3) and as the weight of the item is 2 and the maximum capacity of the subproblem is 3, the item can be added to the knapsack so the second condition of the recursive formula will be used. Hence, 3 will be filled in the matrix as the value of the first item is 3.

i = 1; 
cᵢ = 3; 
wᵢ = 2; 
w = 3; 
w-wᵢ = 1;

Step 6

Similarly, C[1,4] will be filled following the second condition of the recursive formula.

i = 1; 
cᵢ = 3; 
wᵢ = 2; 
w = 4; 
w-wᵢ = 2;

Step 7

Similarly, C[1,5] will be filled following the second condition of the recursive formula.

i = 1; 
cᵢ = 3; 
wᵢ = 2; 
w = 5; 
w-wᵢ = 3;

Step 8

C[2,1]: Now we can take the first 2 items i.e. (2,3) , (3,4) but the maximum capacity of the subproblem is 1 and weights of both the items are 2 and 3 respectively which is greater than the maximum capacity of the knapsack. Therefore, no item can be filled in the bag.

i = 2; 
cᵢ = 4; 
wᵢ = 3; 
w = 1; 
w-wᵢ = -2;

Step 9

C[2,2]: Here we can take the first 2 items (2,3) , (3,4) , the maximum capacity of the subproblem is 2. We can notice that the weights of 2 items that can be chosen is 2 and 3 respectively and since the max capacity is 2 so we will choose the first item and fill in the value of the first item in the matrix.

i = 2; 
cᵢ = 4; 
wᵢ = 3; 
w = 2; 
w-wᵢ = -1;

Step 10

C[2,3]: The first 2 items can be chosen and the maximum capacity of the subproblem is 3. The first 2 items are (2,3) , (3,4) with weights 2,3 respectively. Since the max capacity of the bag is 3 and the weight of the second item is 3 so we will be choosing that item and filling in the matrix with the value of the second item.

i = 2; 
cᵢ = 4; 
wᵢ = 3; 
w = 3; 
w-wᵢ = 0;

Step 11

C[2,4]: Similarly, this cell will be filled following the second condition of the recursive formula.

i = 2; 
cᵢ = 4; 
wᵢ = 3; 
w = 4; 
w-wᵢ = 1;

Step 12

C[2,5]: The first 2 items can be chosen and the maximum capacity of the subproblem is 5. The first 2 items are (2,3) , (3,4) with weights 2,3 respectively. So both items can be added to the bag as the weights of both the items = the weight of the subproblem. The cell will be filled by the sum of the values of both the items (3+4=7).

i = 2; 
cᵢ = 4; 
wᵢ = 3; 
w = 5; 
w-wᵢ = 2;

Step 13

C[3,1]: There is no item amongst the first 3 items that are less than or equal to the maximum capacity of the subproblem, so no item will be added.

C[3,2] and C[3,3] will be filled from the previous cells following the first condition of the recursive formula.

i = 3; 
cᵢ = 5; 
wᵢ = 4; 
w = 1..3

Step 14

C[3,5]: Here first 3 items can be added and the max capacity is 5. The first 3 items are (2,3) , (3,4) & (4,5). So the third item will be chosen as it has the highest value.

i = 3; 
cᵢ = 5; 
wᵢ = 4; 
w = 4; 
w-wᵢ = 0;

Step 15

C[3,5]: The first 3items can be chosen and the maximum capacity of the subproblem is 5. The first 2 items are (2,3) , (3,4) & (4,5) with weights 2,3,4 respectively. So the first two items can be added to the bag as the weights of both the items = the weight of the subproblem. The cell will be filled by the sum of the values of both the items (3+4=7).

i = 3; 
cᵢ = 5; 
wᵢ = 4; 
w = 5; 
w-wᵢ = 1;

Step 16

The cells of the last row will be filled following the the first condition of the recursive formula.

i = 4; 
cᵢ = 6; 
wᵢ = 5; 
w = 1..4

Step 17

C[4,5]: Here all the items (2,3) , (3,4) , (4,5) , (5,6) can be chosen and the maximum capacity of the bag is 5 so those items will be chosen that result in the maximum possible benefit value of the bag. So the first 2 items will be chosen as their values add up to 7 which is greater than any other combination of values possible.

i = 4; 
cᵢ = 6; 
wᵢ = 5; 
w = 5; 
w-wᵢ = 0;

Code

/* A Naive recursive implementation of
0-1 Knapsack problem */
#include <bits/stdc++.h>
using namespace std;// A utility function that returns
// maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }// Returns the maximum value that
// can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{// Base Case
 if (n == 0 || W == 0)
  return 0;// If weight of the nth item is more
 // than Knapsack capacity W, then
 // this item cannot be included
 // in the optimal solution
 if (wt[n - 1] > W)
  return knapSack(W, wt, val, n - 1);// Return the maximum of two cases:
 // (1) nth item included
 // (2) not included
 else
  return max(
   val[n - 1]
    + knapSack(W - wt[n - 1],
      wt, val, n - 1),
   knapSack(W, wt, val, n - 1));
}// Driver code
int main()
{
 int val[] = { 60, 100, 120 };
 int wt[] = { 10, 20, 30 };
 int W = 50;
 int n = sizeof(val) / sizeof(val[0]);
 cout << knapSack(W, wt, val, n);
 return 0;
}//Taken from GFG

Output: 220

This is how this algorithm is used to find the maximum possible benefit value or cost of the knapsack using Dynamic Programming.

Thanks for reading!

Easy Steps To Master 0–1 Knapsack Problem

Written by Tanisha Sharma