0–1 Weighted Knapsack

10 min readMar 15, 2018

The 0–1 Weighted Knapsack(sack) problem is a well studied problem often used as an example for dynamic programming. My issue is that many existing explanations don’t clearly explain why this problem is a candidate for DP and how we arrive to that conclusion. I hope to clear this up here. TLDR; You can read the description for the knapsack problem here — so I won’t reiterate again.

Truths and Assumptions

It doesn’t matter the order in which you select the items.
If you have a optimized knapsack with n items, it’s not always the case that you should always add the (n+1)th item (even if you have capacity).

Recursive Solution First

For each item n, we have to decide to choose or discard it. Since it doesn’t matter the order of insertion, we’ll arbitrary start at the end.

Let’s denote v[n] and w[n] be the value and weight of the nth item respectively.
If we choose item n, the maximum value for 1…n items is the maximum value for 1…n-1 plus v[n]. The capacity of the sack will be decreased by w[n].
If we discard item n, the value of the sack doesn’t change. The sack capacity doesn’t change either.
If we the capacity is less than w[n], we cannot put n into the sack and the only option is to skip it.

We can already see a top-down recursive solution forming here — at each recursive call, we decide to accept item n or not. Then we break the problem into finding the maximum value for the sub-trees starting at node n-1.

Each recursive call, we return the maximum of either accepting item n or not.
Our base case would be when n=0. If capacity is 0, we can no longer add anymore objects, so the value is 0.

// for the sake of sake of brevity, I'm omitting boilerplate code 
int[] values = {10,5,7,12,8,6};
int[] weights = {6,1,2,5,4,3};public int findMaxValue(int itemIndex, int capacity) {
    int weight = weights[itemIndex];
    int value = values[itemIndex];
   
    if (itemIndex == 0 ||  capacity == 0) {
       return 0;
    }else if (weight > capacity) {
       // unable to  accept item as weight exceeds capacity
       return findMaxValue(itemIndex - 1, capacity);
    }else {
       int include = value + findMaxValue(itemIndex - 1, capacity - weight); 
       int notInclude = findMaxValue(itemIndex - 1, capacity);
       return Math.max(include, notInclude);   
    }
}

Analyse the Recursive Solution

If we take a look at the recursion tree, each f(n,c) is a recursive call where n is the item we are currently looking at and c is the capacity of the sack at that moment. We need to notice three things before moving forward:

Each level corresponds to a element. i.e. The third level in this tree always corresponds with deciding to choose or discard the 3rd item.
There are duplicate sub-trees within the tree. This isn’t immediately clear in many token (small) examples, but if you take a look at the values of c within a level, you can grasp duplicates are formed.
Though there are duplicate calls f(n, c), the maximum number of unique calls to f(n,c) at a level is are no more than c.

Runtime complexity: O(n) = O(n-1) + O(n-2) = 2^n

Recursive Solution First With Memorization

The fact that there are duplicate sub-trees makes it a candidate for memorization. The memorization function is indexed by two keys, the item under consideration, n, and the current capacity of the sack, c.

// for the sake of sake of brevity, I'm omitting boilerplate code 
int[] values = {10,5,7,12,8,6};
int[] weights = {6,1,2,5,4,3};public int findMaxValue(int itemIndex, int capacity) {
   
   int weight = weights[itemIndex];
   int value = values[itemIndex];
   
   int max;
   if (memoTable[itemIndex][capacity] > 0 ) {
      return memoTable[itemIndex][capacity];
   }else if (itemIndex == 0 ||  capacity == 0) {
      return 0;
   }else if (weight > capacity) {   
      max = findMaxValue(itemIndex - 1, capacity);
      return max;
   }else {
      int include = value + findMaxValue(itemIndex - 1, capacity - weight); 
      int notInclude = findMaxValue(itemIndex - 1, capacity);
      max = Math.max(include, notInclude); 
   }
    
   // update memorization table
   memoTable[itemIndex][capacity] = max;
   return max;
}

With memorization, the running time is now O(n*c) where c is the capacity of the knapsack. We can see this by looking at the recursion table from our non-memorization algorithm. The maximum number of unique calls to f(n,c) at a particular level of the tree is at most c. This reduces the time complexity from O(2^n) to O(n*c).

Dynamic Programming

Let’s consider the conditions for using DP to find an efficient solution:

Overlapping Sub-problems — Yes. We can see with our memorization algorithm that there are overlapping sub-problems.
Optimal Substructure — Yes. In the recursive solution, observe that at any node in the tree, where we are making the decision on item n, we base it off the maximum value possible for items 1…n-1 (if we select n) with capacity c or the maximum value for those items with capacity c-weight[n] (if we don’t select n) — which are sub-problems we solve first. Thus making the decision to include or discard item n is based on previous solved sub-problems.

The DP Table

In the recursive solution, we return the maximum value of each sub-problem, so a candidate state could be this value. It then follows that the items are a natural consideration for the columns. But with this, for a given item n, we still can’t decide to use or discard it based on any optimal sub-problem solution since this determination is based on both w[n] and capacity of the sack. So we’re missing something…

Recall that the when we make the recursive call in the situation where we choose item n, we need to decrease the capacity by weight[n]. This means capacity also needs to be considered when constructing our DP table…a 2-D table.

Example Inputs

w = [3, 2, 1] v = [5, 3, 4] with capacity c = 5
In order to simply the explanations, we’ll add a 0 item to both the w and v arrays. w = [0, 3, 2, 1] v = [0, 5, 3, 4]

I’m going to use the sample inputs from the this video here. I’m doing this because this set of weights and values offers several nice use-cases (with a small input size) to deal with while filling out the chart.

The DP table c/n, where the columns represent each possible value for the capacity of the sack and the rows represent each possible item. The values are described as (w,v) where w=the weight of the item and v=the value. Thus dp[n][c]=the maximum value obtainable for items 1…n with capacity c. Keep in mind some more definitions:

w[n] represents the weight of item n. i.e. w[3]=1
v[n] represents the value of an item. i.e. v[2]=3
f(n, c) is the maximum value obtainable for items 1…n with capacity c. Remember, this value can be found in our DP table: dp[n,c]

Note: The 1st(n=0) column and row are all 0s. One intuitive reason is because a sack with capacity of 0, cannot hold any items. The other reason is to simplify the algorithm — which you will see at the end.

Fill Row 1

Now to fill in the chart. We’ll start with row 1. In this row, we are considering to put the 1st item into the knapsack or not. We’ll start slow, then speed up as we go on.

At dp[1][1], a sack of capacity 1 cannot hold the item with weight 3 (w[1]) — So the maximum value possible is 0.
At dp[1][2], c=2, we need to discard the item since w[1] > c — so the maximum value possible is still 0.
At dp[1][3], c=3, If we accept the item, the value is 5. If we discard, the value is 0. So the max(5,0)=5 — we choose to accept the item. Since this is the first item we’re considering, we don’t need to consider previous sub-problems.
For the remaining columns, the capacity is greater than 3, we follow the same logic as the previous point — so the maximum obtainable value is 5.

Let’s Fill Row 2

At dp[2][1], c=1. Item 2 has w=3 so we cannot take the item. The maximum value possible is the maximum value for 1 item with capacity 1 which is dp[1][1]=0.
At dp[2][2], c = w[2] = 2. If we choose item 2, the sack’s value is 3. We cannot consider anymore items since the capacity is 0 after choosing th item 2 . If we discard the item, the max value is 0 since the only other item we can hold is item 1, but we cannot choose it since it’s weight is greater than the capacity: w[1] = 3 > c.
At dp[2][3], c=3 so we can choose or discard item 2. We use the state transition formula defined above to determine the maximum value obtainable:

dp[2][4], c=4 follows the same logic as dp[2][3] so it has a maximum value of 5 as well.
At dp[2][5], c=5 we have the choice to choose or discard item 2. The maximum value obtained is 8, when we choose item 2:

Row 3

At dp[3][1], c=1 we can choose or discard item 3. We take the max of
i) v[3] + dp[2][0] = 4 + 0 = 4
ii) dp[2][1] = 0
so we obtain the maximum value when we choose item 3.
At dp[3][2], c=2 we can choose or discard item 3. We take the max of
i) v[3] + dp[2][1] = 4 + 0 = 4
ii) dp[2][2] = 3
so we obtain the maximum value when we choose item 3.
At dp[3][3], c=3 we can choose or discard item 3. We take the max of
i) v[3] + dp[2][2] = 4 + 3 = 7
ii) dp[2][2] = 3
so we obtain the maximum value when we choose item 3.
At dp[3][4], c=4 we can choose or discard item 3. We take the max of
i) v[3] + dp[2][3] = 4 + 5 = 9
ii) dp[2][3] = 5
so we obtain the maximum value when we choose item 3.
At dp[3][5], c=5 we can choose or discard item 3. We take the max of
i) v[3] + dp[2][4] = 4 + 5 = 9
ii) dp[2][5] = 8
so we obtain the maximum value when we choose item 3.

Thus to find the answer, what is the maximum value obtainable we simply have to look at dp[3][5], and the value is 9.

Time Complexity

The time complexity is O(c*n) since we have to fill each value in the table and carry out a constant time calculation at each cell.

The Code

public int findMaxValue(int[] w, int[] v, int capacity) {    // create the DP table
    int[][] dp = new int[w.length][capacity + 1];    // start at n, c = 1 since the first row and column are 
    // always all 0
   for (int n = 1; n < w.length; n++) {
       for (int c = 1; c < capacity + 1; c++) {
           if (w[n] > c) {
               dp[n][c] = dp[n - 1][c];    
           }else {
               int remainingCapacity = c - w[n] < 0 ? 0 : c - w[n];
               int chooseN = v[n] + dp[n - 1][remainingCapacity];
               int discardN = dp[n - 1][c];
              dp[n][c] = Math.max(chooseN, discardN);
           } 
       }
   }
   return dp[w.length - 1][capacity];
}

This algorithm simply builds the 2d array starting at [1][1] building towards [n-1][c] in the manner described above. The time complexity is O(n*c) and the space complexity is also O(n*c) but since we’re not using recursion, the algorithm runs with less space usage by a constant factor.

Note: The 2d array has an extra row and column which we leave all 0s. this allows the algorithm to simply retrieve 0 when we try to obtain dp[n-1][c] when n = 1.

Conclusion

When I first encountered the knapsack problem, I found it pretty tricky and also found existing online explanations frustrating since they didn’t explain the underlying reasoning why you need build the DP table the way it and state transitions. What helped me out the most is to step though the naive solution, add memorization, then try to create the DP solution myself. In the end, I decided to document my procedure here. Hopefully this article helps you out on your own dynamic programming research.