0-1 Knapsack Problem using Dynamic Programming – Pencil Programmer (2024)

Summary: In this tutorial, we will learn What is 0-1 Knapsack Problem and how to solve the 0/1 Knapsack Problem using Dynamic Programming.

Introduction to 0-1 Knapsack Problem

The knapsack 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

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

For example, consider we are given the following 4 weights with respective values.

We are also given a knapsack bag that has a total weight limit of 5.

We have to find the number of each weight to include in the bag so that the total weight is less than or equal to 5 and the total value is as large as possible.

Note: We cannot include the faction of the item, we either include the whole single item or not.

There are multiple ways to solve the 0-1 Knapsack problem, one such method is recursion.

0-1 Knapsack Solution using Recursion (Inefficient Approach)

For each item, we have to decide whether to include it in the knapsack bag.

See Also

0/1 Knapsack Problem - GeeksforGeeks0/1 Knapsack Problem Fix using Dynamic Programming ExampleSolving the Knapsack Problem - A Guide to Dynamic ProgrammingSolve 0-1 Knapsack Problem (using Dynamic Programming)

To make this decision, we compare the total value of the bag when including the item with the value when not including the item.

Since for every item we have to repeat the same process, we use recursion.

#include <iostream>//Weightsint weight[] = {0, 1, 2, 1, 3};//valuesint value[] = {0, 10, 7, 11, 15};//recursive funcitonint knapsack(int n, int KW){ //base condition if(n<=0 || KW<=0) return 0; //don't select item if its weight is greater than knapsack weight else if(weight[n]>KW) return knapsack(n-1, KW); //check which gives more value //1. When not including the nth item //2. When including the nth item else{ //total value when not including the item int not_include_nth_item = knapsack(n-1, KW); //total value when including the item int include_nth_item = value[n] + knapsack(n-1, KW-weight[n]); //return the larger value return std::max(not_include_nth_item, include_nth_item); }}//Driver codeint main() { //knapsack(<number_of_items>, <knapsack_weight>) std::cout << knapsack(4, 5);}

The above program has two successive recursive calls within the function:

1. knapsack(n-1, KW) – Total value when not including the n^th item.
2. knapsack(n-1, KW – weight[n]) – Total value when including the n^th item.

This exponentially increases the time complexity of the program to O(2ⁿ).

We can definitely improve the efficiency of our program by incorporating other techniques.

The 0-1 Knapsack problem can be solved using the greedy method however using dynamic programming we can improve its efficiency.

0-1 Knapsack Solution using Dynamic Programming

The idea is to store the solutions of the repetitive subproblems into a memo table (a 2D array) so that they can be reused i.e., instead of knapsack(n-1, KW), we will use memo-table[n-1, KW].

But, what is the subproblem here?

For instance, when deciding on the 4th item (whether to include it or not) we recursively make decisions for all the preceding items (i.e., 3^rd, 2^nd, and 1^st items) twice.

See Also

Solving the Knapsack Problem with Dynamic Programming

When deciding on the 3rd item, the decisions of the preceding items are made once again, although they were computed initially while making the decision for the 4^th item.

This computation of the maximum value for the n^th item is the subproblem here, which is computed repeatedly.

When calculated for the first time we store the corresponding value of Knapsack(N-1, KW) into the memo table and reuse if needed

Now the question arises, how the memo table will look like or supposed to have?

Note: The size of the memo table is (Total number of items + 1) * (Knapsack Weight+1).

In the memo table:

• Row – is the number of items we can take. The firstrow is 0, it means no item is available. The secondrow is 1, it means only the 1st item is available. Similarly, Third-row is 2, it means only 1st and 2nd item are available…Forth row tells that all 4 items should be considered for computing the total value for the given knapsack weight.
• Column – is the knapsack weight. The firstcolumn is 0, it means the knapsack bag is not available. The second column is 1. it means the value of knapsack weight is 1, therefore we can only take those items whose total weights sum up to 1. The fourthcolumn (Last column) is 5, which is what we want, the total weight in the knapsack bag.

Each table cell stores the solution of a subproblem. For instance, memo-table[3][2] = 21 means for a knapsack bag of weight equal to 2, the maximum value that can be achieved with the first 3 items is 21.

As we have a memo table available with us, we iterate through its cells and use the previously stored values to calculate the values for the current cell.

Here is the implementation of the discussed dynamic programming solution:

#include <iostream>#define MAX 200using namespace std;//weightsint weight[] = {0, 1, 2, 1, 3};//valuesint value[] = {0, 10, 7, 11, 15};//knapsack bag weight limitint knapsack_weight = 5;//count of itemsint n = 4;class KnapsackDP{public: int **memoTable; KnapsackDP(){ // memo table this->memoTable = new int*[n+1]; //Initiale each cell with 0 for(int i=0; i<n+1; i++){ this->memoTable[i]= new int[knapsack_weight+1] {0}; } } int solve(){ //Compute and fill the memo table for(int i=1; i< (n + 1); i++){ for(int j=1; j<(knapsack_weight + 1); j++){ //when not including the item int not_taking_item = memoTable[i-1][j]; //when including the item int taking_item = 0; if(weight[i] <= knapsack_weight){ if(j-weight[i] < 0) taking_item = memoTable[i-1][j]; else taking_item = value[i] + memoTable[i-1][j-weight[i]]; } //store the larger value in the table memoTable[i][j] = max(not_taking_item, taking_item); } } //return the max value for the given knapsack weight return memoTable[n][knapsack_weight]; } //Function output the included items void selected_items(){ for(int i=n, j= knapsack_weight; i>0; i--){ if(memoTable[i][j] != memoTable[i-1][j]){ cout << "Item: "<<i <<" Selected \n"; j = j- weight[i]; } } }}; int main(){ KnapsackDP kdp; cout << "Total Benefit: "<< kdp.solve() <<endl; //To print which items are included kdp.selected_items(); return 0;}

public class Main{ public static void main(String args[]){ //weights int weight[] = {0, 1, 2, 1, 3}; //values int value[] = {0, 10, 7, 11, 15}; //Taking Knapsack weight as 5 KnapsackDP kdp = new KnapsackDP(5, 4, weight, value); System.out.println("Total Benefit: "+kdp.solve()); //To print which items are selected kdp.selected_items(); }} class KnapsackDP{ int knapsack_weight; int n; int weight[]; int value[]; int memoTable[][]; public KnapsackDP(int W,int N,int weight[],int value[]){ this.knapsack_weight = W; this.n = N; this.weight = weight; this.value = value; this.memoTable = new int[N+1][W+1]; } public int solve(){ //compute and fill the table for(int i=1; i< (n + 1); i++){ for(int j=1; j<(knapsack_weight + 1); j++){ //when not including the item int not_taking_item = memoTable[i-1][j]; //when including the item int taking_item = 0; if(weight[i] <= knapsack_weight){ if(j-weight[i] < 0) taking_item = memoTable[i-1][j]; else taking_item = value[i] + memoTable[i-1][j-weight[i]]; } //store the larger value in the memo table memoTable[i][j] = Math.max(not_taking_item, taking_item); } } //return the max value for the given knapsack weight return memoTable[n][knapsack_weight]; } //Function to output included items public void selected_items(){ for(int i=n, j= knapsack_weight; i>0; i--){ if(memoTable[i][j] != memoTable[i-1][j]){ System.out.println("Item: "+i+" Selected"); j = j- weight[i]; } } }}

The time complexity of the program is O(n²) i.e, much better than the recursive solution.

How to know which item is included in the bag?

To know which item is selected for calculating total Benefit/Value, start from the last row and column index.

Go one level up and check whether the value in the upper level is smaller or not.

if(memoTable[i][j] != memoTable[i-1][j])

• If YES, then it means that the difference is caused because of including the last item (4th item in our case). Now subtract the weight of the last (selected) item from j and repeat the same process for the resultant value of the jth column.
• If NO, then go one level up more and check for the difference in the value. Keep going up until you see the difference in the value.

Output:

In this tutorial, we learned to solve the 0-1 knapsack problem using the dynamic programming algorithm in C++ and Java programming languages.