0-1 Knapsack Problem


Reading time: 20 minutes | Coding time: 10 minutes

Given n items, in which the ith item has weight wi and value vi, find the maximum total value that can be put in a knapsack of capacity W. You cannot break an item, either pick the complete item, or don't pick it.


Solution

We first start by building a table consisting of rows of values and columns of weights.
Starting from the first row and column, we keep on filling the table till the desired value is obtained.

Let the table be represented as $dp[n, w]$ where $n$ is the number of items to be included and $w$ is the left over space in the bag.

For every object, there can be two possibilities:

  • if the object's weight is greater than the leftover space in the bag,
    then $dp[n, w]$ = $dp[n - 1, w]$
  • else,
    the object might be taken or left out.
    • if it is taken, the total value of the bag becomes $dp[n, w]$ = $vn$ + $dp[n - , w - wn]$, where vn is value of the $n$th object and $wn$ is its weight.
    • if the object is not included, $dp[n, w]$ = $dp[n - 1, w]$

The value of $dp[n,w]$ is the maximum of both these cases.

In short, the optimal substructure to compute $dp[n, w]$ is:

dp[n, w] = dp[n-1, w], if wn > w
         = max( dp[n-1, w], vn + dp[n-1, w - wn] ), otherwise

Complexity


  • Time complexity: Θ(n*W)
  • Space complexity: Θ(n*W)

Implementation


  • Java

Java


import java.util.Scanner;
import java.lang.Math;
    public class Solution {
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            int n = s.nextInt();
            int W = s.nextInt();
            int val[] = new int[n];
            int weight[] = new int[n];
            for(int i = 0;i<n;i++) val[i] = s.nextInt();
            for(int i = 0;i<n;i++) weight[i] = s.nextInt();
            int dp[][] = new int[n+1][W+1];
            for(int i = 0;i<=n;i++) {
                for(int w = 0;w<=W;w++) {
                    if(i==0||w==0) continue;
                    if(weight[i-1]>w) dp[i][w] = dp[i-1][w];
                    else dp[i][w] = Math.max(val[i-1]+dp[i-1][w-weight[i-1]], dp[i-1][w]);
                }
            }
            System.out.println(dp[n][W]);
        }
}

Example

Input:
4
7
1 4 5 7
1 3 4 5

Output:
9

for this input, the final dp array will be constructed as

0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1
2 0 1 1 4 5 5 5 5
3 0 1 1 4 5 6 6 9
4 0 1 1 4 5 7 8 9

here, the rows 1,2,3,4 correspond to items (val)weight - (1)1, (4)3, (5)4, (7)5 respectively and the columns 0,1,2...7 correspond to remaining weight in the bag.


References/ Further reading

  1. https://github.com/OpenGenus/cosmos/tree/master/code/dynamic_programming/src/knapsack