0-1 Knapsack Problem

November 6, 2021

0-1 Knapsack Problem

In 0-1 Knapsack Problem, we are asked to fill a knapsack according to some constraints. This problem and its variations are one of the most asked interview problems. In this article, we explain the solution to the problem with c++ implementation.

0-1 Knapsack Problem

0-1 Knapsack Problem Description

We are given a knapsack which has a capacity of C ie the knapsack can carry items of total weight less than or equal to C. Each item has a weight and value/price associated to it. We are given n items, determine the maximum value of the knapsack we can obtain by filling some subset of the n items.

Input:

  • First line contains an integer C, the capacity of the knapsack.
  • Second line contains a single integer n, the number of items.
  • Third line contains n integers, the value of n items. Value is ith item is ith integer.
  • Fourth line contains n integers, the weight of n items. Weight of ith item is ith integer.

Output:

  • Single Integer, the maximum value obtainable.

0-1 Knapsack Problem Solution

Memoization or Top Down Solution

To build a top down solution we must follow the following steps –

  • Break Down the Problem – In this step we try to break down the problem into smaller problems and assume recursion will solve the smaller problems.

F(C,N) = Maximum value of filling C capacity knapsack with N items.

This can be broken down into two cases – when we put the nth item in the knapsack or we discard the nth item.

Thus,

F(C,N) = F(C,N-1)   { if (weight[N] > C We can’t include this item))}

F(C,N) = max(F(C,N-1) , value[n] + F(C-weight[N],N-1))   {We don’t include or we include}

 

  • Find the base case- Now we have to find the base case. It is easy as we can’t include items if C = 0 ie capacity of knapsack is zero or N = 0 ie we don’t have items left to process.
  • Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping sub problems properties can be visualized below.

 

0-1 Knapsack Problem memoization

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int memo[1005][1005];
int knapSack(int C, int wt[], int val[], int n)
{
    if (n == 0 || C == 0)
        return 0;

    if (memo[C][n] != –1)
        return memo[C][n];

    if (wt[n – 1] > C) // We can’t include the nth item
    {
        return memo[C][n] = knapSack(C, wt, val, n – 1);
    }

    int op1 = val[n – 1] + knapSack(C – wt[n – 1], wt, val, n – 1); // Include nth item (at n-1 index)
    int op2 = knapSack(C, wt, val, n – 1);// Don’t Include

    return memo[C][n] = max(op1, op2);
}
int main()
{
    memset(memo, –1, sizeof memo);

    int val[] = {10, 20, 10, 20};
    int wt[] = {2, 1, 2, 2};
    int C = 3;
    int n = sizeof(val) / sizeof(val[0]);

    cout << knapSack(C, wt, val, n) << endl;
    return 0;
}

Output:

40

Bottom Up Solution

In this approach we solve smaller problems first instead of shoving for bigger problems. We create a dp table of size N*W where

dp[i][w] = maximum value of filling w capacity knapsack with i items.

Using similar transitions as above we can get our answer.

0-1 Knapsack Problem Bottom Up SOlution

C++ Code:

#include <bits/stdc++.h>
using namespace std;
int knapSack(int C, int wt[], int val[], int n)
{
    int dp[n + 1][C + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int w = 0; w <= C; w++)
        {
            if (i == 0 || w == 0) // Base Case
                dp[i][w] = 0;
            else if (wt[i – 1] > w) // We cannot include ith tiem
                dp[i][w] = dp[i – 1][w];
            else // We can include ith tiem
                dp[i][w] = max(val[i – 1] + dp[i – 1][w – wt[i – 1]], dp[i – 1][w]);
        }
    }
    cout << “Ans -> “;
    return dp[n][C];
}

int main()
{
    int val[] = {10, 20, 10, 20};
    int wt[] = {2, 1, 2, 2};
    int C = 3;
    int n = sizeof(val) / sizeof(val[0]);

    cout << knapSack(C, wt, val, n) << endl;
    return 0;
}

Output:

Ans -> 40