Knapsack Problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The brute force approach is to form all possible combinations of items and consider only those subsets whose total weight is equal to or less than the total knapsack weight W, out of the chosen subsets pick the subset whose value is maximum.

Given two integer array of wt: [1, 2, 3] and val: [20, 5, 30] representing weight and value, below are the possible combination of items along with their weight and value:

{1} -> wt: 1, value: 20
{2} -> wt: 2, value: 5
{3} -> wt: 3, value: 30
{1, 2} -> wt: 1 + 2 = 3, value: 20 + 5 = 25
{1, 3} -> wt: 1 + 3 = 4, value: 20 + 30 = 50
{2, 3} -> wt: 2 + 3 = 5, value: 5 + 20 = 25
{1, 2, 3} -> wt: 1 + 2 + 3 = 6, value: 20 + 5 + 30 = 55

Now depending on the total Knapsack Capacity, we can pick appropriate subsets.
For a knapsack capacity of 1, only first subset {1} can be chosen.
However, for a knapsack capacity of 4, there are 5 subsets whose total weight is less than or equal to 4: {1}, {2}, {3}, {1, 2}, {1, 3}, out which {1, 3} has maximum value of 50, hence we will pick that subset.
Brute force algorithm will involve all sets, and the total number of combinations of all sets is equal to 2^numOfItems.

To find the optimal substructure which has the maximum value, we have to consider each item and for every item we have only two possible cases.
case 1: Item is considered.
case 2: Item is NOT considered.

We have to pick that case which will result in higher value:
case 1: If item is consider, the total value will increase by that item’s value and knapsack capacity will reduce by that item’s capacity.
case 2: If item is NOT consider, value and knapsack capacity will NOT change.

After considering that item, we move on to next item. The recursive solution to above approach is:

public static int knapsack(int W, int [] wt, int [] val, int numOfWts) {
	if (numOfWts == 0 || W <= 0) {             
            return 0;
        }
        if (wt[numOfWts - 1] > W) {
            return knapsack(W, wt, val, numOfWts - 1);
	}
	return max(
	    (val[numOfWts-1]+knapsack(W-wt[numOfWts-1],wt,val,numOfWts-1)),
	    knapsack(W, wt, val, numOfWts - 1)
	);
}

If we draw a recursion tree for the above recursive approach for a knapsack problem K(n,W) where n is number of items and W if knapsack capacity.

wt: {1, 2, 3} val: {1, 2, 3}, W=2
                         K(3, 2) 
                     /            \ 
                   /                \               
             K(2,2)                   K(2,1)
            /      \                  /    \ 
          /          \              /        \
       K(1,2)      K(1,1)        K(1,1)     K(1,0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)

We are evaluating K(1, 1) twice, this shows that the sub-problems are overlapping. Since knapsack has both optimal substructure and overlapping subproblem this can be solved using DP approach of using a memoization/lookup table.

The lookup table K[n][W] can be constructed bottom UP where n is number of items and W is total knapsack capacity.

To build the table, we start with 1st item and compute the maximum value with increasing knapsack capacity. We introduce a new item and recalculate maximum values again.

public static int knapsackDP(int W, int[] wt, int[] val) {
    int[][] K = new int[wt.length + 1][W + 1];

    for (int i = 0; i <= wt.length; i++) {
        for (int w = 0; w <= W; w++) {
            //base case, either 0 items or no knapsack capacity.
            if (i == 0 || w == 0) {
                K[i][w] = 0;
            }
            //this item can be considered.
            else if (wt[i - 1] <= w) {
                //max of:
                K[i][w]=max(
//case1:value of that item + remaining items with reduced knapsack capacity
                    val[i - 1] + K[i - 1][w - wt[i - 1]], 
//case2: without this item, value and capacity remains same.
                    K[i - 1][w]
                );
            } 
            //weight of that item is higher current knapsack capacity.
            else {
                K[i][w] = K[i - 1][w];
            }
        }
    }
    return K[wt.length][W];
}

Knapsack lookup table for wt: {1, 1, 1, 1 , 1} and value: {1, 1, 1, 1, 1} and W=5 is:
Knapsack table:
[0 0 0 0 0 0 ]
[0 1 1 1 1 1 ]
[0 1 2 2 2 2 ]
[0 1 2 3 3 3 ]
[0 1 2 3 4 4 ]
[0 1 2 3 4 5 ]

Where row is item and column is knapsack capacity. When item is 0 (row = 0) or knapsack capacity is 0 (column = 0), the total knapsack maximum value is 0.

Hence 1st row and 1st column values are all 0s.
2nd row: there is only 1 item to be consider hence increasing knapsack capacity is not increasing total value and the value is constant at 1.
3rd row: now we are considering 2 items each of weight 1, hence from column 3 when total knapsack capacity is 2, both items can be put in knapsack and total value of knapsack increases from 1 to 2, but it stays at 2 since both items are consider, hence 2nd row is: [0 1 2 2 2 2]
Finally for the last 5th row: when all items are available, with increasing knapsack capacity (column), each additional item can be added to be knapsack thereby increasing its value: [0 1 2 3 4 5]

The above DP approach has a time complexity of O(nW)

Git:
algorithms/src/main/java/org/nmn/notes/algorithms/dp/Knapsack.java

Reference:
https://en.wikipedia.org/wiki/Knapsack_problem

Advertisements