Categories

# Dynamic Programming: Knapsack Problem

In the knapsack problem, a thief is filling up their knapsack with items that weigh differently and have various weights. The thief must design an algorithm that will help them determine what combination of items to carry that have maximum value without breaking their knapsack that can only hold up to limited weight.

My high school Principal used to tell us a story of two people taken to the supermarket and asked to fill their trolleys with whatever they would like. The fool, my principal would say, would rush to the food and groceries section and fill up their trolley with bread, cabbages, and soda. The wise person, on the other hand, would rush to the jeweler section and fill up their trolley with expensive diamond wristwatches, gold rings, and pearl necklaces. That, in essence, is the knapsack problem.

In the knapsack problem, a thief is filling up their knapsack with items that weigh differently and have various weights. The thief must design an algorithm that will help them determine what combination of items to carry that have maximum value without breaking their knapsack that can only hold up to limited weight.

Example to show thought process

For example, you have items of the following weights:

[6,5,10,3]

And the items have the following respective values

[20,15,25,10]

And your knapsack has a maximum weight of 10.

We can derive the maximum value by combining the items of weight 6 and 3, which is acceptable as it gives us a total weight of 9 which is less than our knapsack capacity of 10. From this, we derive the maximum value of 30 (20 +10).

Brute force approach

The first approach we can try is simply looking at each item and determining individually whether we will take it or leave it. For each item, we will have two new situations. One where we take the item, or one where we don’t. Because we are taking the maximum between these two scenarios, then we will compare them and take the maximum.

Take the above example, for instance:

maxWeight = 10

values = [20, 15, 25, 10]

weights = [6, 5, 10, 3]

The first item weighs 6. So we can take it, or not. If we do take it, our maxWeight changes to 4. Then we look at the next element, of weight 5. We cannot take it, since it will exceed our max weight of 4. Same as the next element of weight 10. But we can take weight 3, which will fit in our knapsack. We can also decide not to take 4, returning a 0 up the chain.

Then we consider the scenario where we did not take 6 in the first place. Here we move to the second element, 5. We can take it, since it is less than 10. We then proceed further down considering each scenario twice recursively as we have done above.

Analysis of Asymptotic complexity of brute force approach

The recursion tree has n levels. The maximum call stack size is therefore n. The space complexity is therefore O(n), linear space.

Example of Brute Force Approach

``````import java.lang.*;
import java.io.*;

public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int a, i, k, n, b, Capacity, tempWeight, tempValue, bestValue, bestWeight;
int remainder, nDigits;
int Weights[] = {1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1};
int Values[] = { 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };
int A[];

A = new int;

Capacity = 20; // Max pounds that can be carried
n = 16;  // number of items in the store
b=0;

tempWeight = 0;
tempValue = 0;
bestWeight = 0;
bestValue = 0;

for ( i=0; i<65536; i++) {
remainder = i;

// Initialize array to all 0's
for ( a=0; a<16; a++) {
A[a] = 0;
}

// Populate binary representation of counter i
//nDigits = Math.ceil(Math.log(i+0.0));
nDigits = 16;

for ( a=0; a<nDigits; a++ ) {
A[a] = remainder % 2;
remainder = remainder / 2;
}

// fill knapsack based upon binary representation
for (k = 0; k < n; k++) {

if ( A[k] == 1) {
if (tempWeight + Weights[k] <= Capacity) {
tempWeight = tempWeight + Weights[k];
tempValue = tempValue + Values[k];
}
}
}

// if this knapsack is better than the last one, save it
if (tempValue > bestValue) {
bestValue = tempValue;
bestWeight = tempWeight;
b++;
}
tempWeight = 0;
tempValue = 0;
}
System.out.printf("Weight: %d Value %d\n", bestWeight, bestValue);
System.out.printf("Number of valid knapsack's: %d\n", b);
}
}``````

In the above, we recursively call the function twice on each element in an array of size n. This gives us a time complexity of O(2n), exponential time

An advantage of brute forcing this problem is that we save on space. We do not have to create an object to store the values at each turn for later retrieval, thus we save on that space and achieve a space complexity of O(n).

The above time complexity is too slow, so we have to optimize it using dynamic programming. Exponential time is one of the worst complexities you can get since with each additional value, we take the squared of all elements just to compute it.

Dynamic Programming

The dynamic programming approach is similar to the brute force but differs in one key way. In dynamic programming, we hash (store) all the values for the element combinations as we go down the tree. This means that instead of recalculating a problem, we store each combination in a set or an object if we calculate it once. Then we just look up if we have calculated that value before and return it, without having to recalculate it once more.Here’s the code for the DP approach in Java

``````
Public class Knapsack2 {

static int knapSack(int capacity, int weights[], int values[], int n) {

// initializing variable to tell us how often the method is accessed.

int numKnaps = 0;

// initializing array for dynamic programming to track the optimal solution.

int[] dp = new int[capacity + 1];

// initializing variable for best weight.

int bestWeight = 0;

// Loop through the array of weights.

for (int i = 1; i < n + 1; i++) {

// track the number of times the method is accessed.

numKnaps++;

for (int tempWeight = capacity; tempWeight >= 0; tempWeight--) {

// Operation to find the best weight.

bestWeight = capacity - dp[tempWeight];

if (weights[i - 1] <= tempWeight) {

// Finding maximum value of the current weight and the current weight plus the

// next weight.

dp[tempWeight] = Math.max(dp[tempWeight], dp[tempWeight - weights[i - 1]] + values[i - 1]);

}

}

}

// Printing statements required by assignment and returning maximum value.

System.out.printf("Weight: %d\n Value: %d\n", bestWeight, dp[capacity]);

System.out.printf("Number of valid knapsack's: %d\n", numKnaps);

return dp[capacity]; // returning the maximum value of knapsack

}

// Main method to drive the program.

public static void main(String[] args) {

int values[] = { 10, 5, 30, 8, 12, 30, 50, 10, 2, 10, 40, 80, 100, 25, 10, 5 };

int weights[] = { 1, 4, 6, 2, 5, 10, 8, 3, 9, 1, 4, 2, 5, 8, 9, 1 };

int capacity = 20;

int n = values.length;

knapSack(capacity, weights, values, n);

}

}``````

Analysis of Asymptotic complexity of dynamic programming approach

The time analysis here is a bit more complex as it depends of changing parameters.

These parameters are the iterator, I, which can be between 0 and n, meaning it has n possible values in the worst case. maxWeight, m, can be between 0 and maxWeight of the backpack, meaning it has maxWeight possible values.

The time complexity is therefore the product of this, O(n * maxWeight).

Same thing for space complexity, , O(n * maxWeight). 