0/1 Knapsack problem example with recursion and dynamic programming solutions

A farmer wants to sell his farm products in the city. He has a knapsack with the capacity of “N” kgs weight, and he has products with more than ‘N’ kgs weight. He wants to fill his backpack in such a way that he gets more money after selling the products in the knapsack. Here 0/1(zero or one) means either pick the product or ignore. We can’t cut the product.

For example a knapsack with “8” Kgs capacity and products like {2,5}, {5,13}, {3,4}, {1,2}, {6,14} which are {weight, costs} respectively. Let’s see below picture to get better understanding.

At max the Knapsack can hold products with value 20.

Here the capacity of the Knapsack and weight, costs of products are given as inputs to the problem.

// Inputs
8 // is capacity of the Knapsack
5 // Number of products
2, 1, 3, 5,  6  // Weights of respective products
5, 2, 4, 13, 14 // Costs of the respective products

// Output ( we need to get the maximum price that we can make using knapsack.
20 // We can get at max 20 units by using the 8kg knapsack.

We can solve this problem using below two approaches.

  1. Recursion.
  2. Dynamic Programming.

Recursion solution

This problem is like a coin change problem where we either can pick the coin or ignore it, 0/1 knapsack mean either we choose a product or ignore it.

We can make a recursive formula for this problem, there are two choices we can have with a product, either we can pick it or ignore it. Finally, we need to maximize the cost between both. The recursion formula is like

F({items}, capacity, currentItem) = 
    maximum { (current Item value + 
    F({items}, capacity - weight of current item, currentItem+1)),

    F({items}, capacity, currentItem+1) }

Maximum value we can make by picking the product or ignoring it.

Code for this recursive approach is as follows

int maxCostKnapsackUsingRec(vector<Item> items, int knapsackWeight, int currItem)
{
    if (knapsackWeight == 0 ||
        currItem == items.size())
    {
        return 0;
    }
    Item item = items.at(currItem);
    if (item.weight > knapsackWeight)
    {
        return maxCostKnapsackUsingRec(items, knapsackWeight, currItem + 1);
    }
    int maxCostIfPick = item.cost +
                        maxCostKnapsackUsingRec(items, knapsackWeight - item.weight, currItem + 1);
    int maxCostIfNotPick =
        maxCostKnapsackUsingRec(items, knapsackWeight, currItem + 1);

    return max(maxCostIfNotPick, maxCostIfPick);
}

This recursive approach runs with an exponential complexity, which is O(2^N). To overcome this runtime complexity drawback, we can come up with a solution using Dynamic Programming. Let’s see how that will work.

Dynamic Programming

We need to memorize the solution at each part of the weights. Let’s see below the dynamic memorization for our problem.

012345678
(2,5)005555555
(5,13)0055513131818
(3,4)0055513131818
(1,2)0257713151820
(6,14)0257713151820
The value at the last cell gives the answer as it uses all products to fill in the knapsack.

Let’s see the formula and code for the dynamic programming approach solution.

dp[i][j] = dp[i-1][j]    // if weight of product is < current weight.
         = max{ dp[i-1][j],
                dp[i-1][j-weight[i]] + cost of j item } // Otherwise.
int maxCostKnapsackUsingDP(vector<Item> items, int knapsack)
{
    int size = items.size();
    int dp[size][knapsack + 1];
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j <= knapsack; j++)
        {
            if (j == 0)
            {
                dp[i][j] = 0;
                continue;
            }
            Item item = items.at(i);
            if (i == 0)
            {
                dp[i][j] = (j < item.weight) ? 0 : item.cost;
            }
            else
            {
                if (j < item.weight)
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j],
                                   dp[i - 1][j - item.weight] + item.cost);
                }
            }
            cout << dp[i][j] << "  ";
        }
        cout << endl;
    }
    return dp[size - 1][knapsack];
}

Complexity of this solution is O(Items*Capacity). Complete code with main function is as showing below.

// Output
0/1 Knapsack problem using Recursion: 
20
0/1 Knapsack problem using Dynamic Programming: 
20

It is all about the 0/1 Knapsack problem with both recursive and dynamic programming approaches. If you know any better solution, please let our readers know by commenting here below. Happy Learning!.

See more:
Advertisements