0-1 Knapsack Problem


Reading time: 30 minutes | Coding time: 10 minutes

Knapsack Problem is a common yet effective problem which can be formulated as an optimization problem and can be solved efficiently using Dynamic Programming. The general task is to fill a bag with a given capacity with items with individual size and benefit so that the total benefit is maximized. The capacity of the bag and size of individual items are limitations. The 0 - 1 prefix comes from the fact that we have to either take an element or leave it.

We show that a brute force approach will take exponential time while a dynamic programming approach will take linear time.

Mathematical statement:

Given a set of N items each having two values (Ai , Bi). We have another value W. The problem is to find a subset of the N items such that:

  • The sum of B attribute of the selected items is maximized
  • The sum of A attribute of the selected items is less than or equal to W

Formal statement:

We are given N items, in which the i th item has weight Wi and value Vi, find the maximum total value that can be put in a knapsack/ bag of capacity W. You cannot break an item, either pick the complete item, or don't pick it.

Example

Suppose we have three items which is defined by a tuple (weight, benefit). The items are:

(7, 12) ; (3, 2), (20, 41) (3, 10) (3, 2)

We have a bag with capacity 29. In this case, the optimal filling will be:

Item 3 + 2 + 4 + 5

Note the total benefit is (41 + 2 + 10 + 2) = 55 with total weight being 29 (= 29).

We could have covered all the weight like:

Item 3 + 1

The total weight will become 27 (< 29) but the benefit will be (41 + 12) = 53 (< 55)

Hence, in the previous combination, we have taken the optimal distribution.

Brute Force Approach

The brute force approach is to generate all subsets and check which subset generates the maximum benefit while maintaining the total weight. This follows the name of the problem 0 1 Knapsack problem where:

  • 1 denotes that an item has been considered
  • 0 denotes that item has not been considered

As there are N items and each item can take two values 0 or 1, the number of combinations become 2^N.

Pseudocode :

maxProfit = 0
for i = 0 to 2^N:
    bin = binary(i)                 // Convert the number to binary
    profit = 0
    weight = 0
    for j = 0 to bin.length():
        if bin[j] is set:           // If the bit j is set, we have to include that item.
            if weight + wt[j] > W:  // When weight of the combination exceeds Capacity, Break.
                profit = 0
                break
            profit = profit + val[j]
            weight = weight + wt[j]
     maxProfit = max(maxProfit, profit)  // Update max profit.      

This way, choosing from all combination would mean a time complexity of order

Θ(2^N)

as there are total 2^n possible combinations of n items.

Dynamic Programming approach

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

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