0-1 Knapsack Problem

Introduction

0-1 Knapsack problem is a kind of knapsack problem which is used to understand dynamic programming approach. Unlike its brother: fractional knapsack, greedy does not guarantee an optimal solution for this problem. It is solved using dynamic programming. Here, we can either pick up an object or leave it. We are not allowed to pick fractions of an object.

Problem Description

Suppose that we are given n objects having a weight and a value associated with them. We are also given a knapsack with capacity = maxWeight. Our goal is to get maximum profit out of these objects by picking those with most value and least weight while also keeping in mind that we do not overshoot our maxWeight. Each object can only be selected once or not selected at all.

For example :

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

In this case, the objects having weights 3 and 1 with values 2 and 3 will have total value = 5. Which is the maximum.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum.

Why not Greedy?

Greedy works for fractional knapsack but not for 0-1 knapsack. Here is an example that disproves greedy approach for 0-1 knapsack. Assume that W=6 and items are:

Item   Value   Size   Value/Size
A       5.5       4         1.38
B       4          3         1.33
C       4          3         1.33

For 0-1 knapsack, if you apply greedy approach, you pickup that item with highest value/size ie. item A. Since A has a size of 4, you only have space of 2 left. Now, you cannot pick any more items. That means that the only thing you have in your bag is Item A which is a total value of 22.

On the other hand, if you had not been greedy and taken the most valuable item and had instead taken Item B, then you would have enough room to take Item C as well. This would have resulted in a total value of 24 in the bag, which is better than the greedy route.

Dynamic Approach

We will use a 2D array for storing solutions to the smaller sub-problems which will help us in calculating the final answer.Here we do the same two operations stated in the recursive approach:

1. PICK UP THE OBJECT

   If we decide to pick up the i(th) object, profit will become value of that object + optimized answer for the remaining weight ie. value[i] + dp[i-1][c-weight[i]]

2. LEAVE THE OBJECT

   If we decide to leave the object, the profit will be the optimized answer for that weight ie. dp[i-1][c]

The answer for a particular object will be the maximum of these 2 values.

MAIN CONDITION:

dp[i][c] = max (dp[i-1][c], profits[i] + dp[i-1][c-weights[i]]);

int knapsack(int v[], int w[], int n, int W)
{
    int T[n+1][W+1];
    for (int j = 0; j <= W; j++) {
        T[0][j] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            if (w[i-1] > j) {
                T[i][j] = T[i-1][j];
            }
            else {
                T[i][j] = max(T[i-1][j], T[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return T[n][W];
}

Time Complexity : O(n*W).\
Space Complexity : O(n*W). We used 2-d array T as extra space