0-1 Knapsack Problem

This is a C++ Program that Solves 0 1 Knapsack Problem using Dynamic Programming technique.

Problem Description

Given weights and values of n items, put these items in a knapsack of capacity M to get the maximum total value in the knapsack.

Note that, you can select items, the sum of whose weight is less than or equal to the capacity of knapsack, W.

Problem Solution

The problem is to find a subset of items such that –

the sum of weight of all the items in the subset should be less than or equal to knapsack capacity
out of all subsets that satisfy criteria 1 above, the desired subset is the one in which the sum values of its items is maximum.

consider this example-
n=3
w[]=3 2 1
v[]=5 3 4

M=5

Create a matrix of order (n+1)*(M+1), ie. knapsack[n+1][M+1]
knapsack[i][j]=maximum attainable value of items in the knapsack with i available items and capacity of knapsack being j.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

Initialize –
knapsack[0][j]=0 for 0<=j<=M
knapsack[i][0]=0 for 0<=i<=n
Now, start filling the matrix row wise, following the given recursive formula –

knapsack[i][j]=

knapsack[i-1][j] , if w[i]>j
max{knapsack[i-1][j], v[i]+knapsack[i-1][j-w[i]] } , if w[i]<=j

The time complexity of this solution is O(n*M).

Expected Input and Output

Case-1:

number of items, n=4
 
weight of items, w[]=2 3 4 5
value of items,  v[]=3 4 5 6
 
capacity of knapsack, M=5
 
maximum attainable value of items=7 
by collecting first and second item in the knapsack

Case-2:

Participate in Data Structure I Certification Contest of the Month Now!

 
n=3
w[]=3 2 1
v[]=5 3 4
 
M=5
 
maximum attainable value of items=9 
by collecting first and last item in the knapsack

Case-3:

 
n=5
w[]=1 2 3 2 2
v[]=8 4 0 4 3
 
M=4
 
maximum attainable value of items=13

Program/Source Code for recursive solution

Here is source code of the C++ Program to Solve 0 1 Knapsack Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
using namespace std;
```
```
 
```

//function to recursive check every subset of items

int knapsack(int w[], int p[], int n, int M)

```
{
```

    //In every pass, we can either include nth item or not

```
 
```

    //if the capacity of knapsack is left to NIL, no value can be attained

```
    if(M==0)
```
```
        return 0;
```
```
 
```

    //if no more items are left, no value can be attained

```
    if(n==0)
```
```
        return 0;
```
```
 
```

    //if current item, weighs more than the capacity of knapsack, it can not be included

```
    if(w[n-1]>M)
```
```
        return knapsack(w,p,n-1,M);
```
```
 
```

    //else select the maximum value of once including the current item and once not including it

    return max(knapsack(w,p,n-1,M),p[n-1]+knapsack(w,p,n-1,M-w[n-1]));

```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
    int M;  //capacity of knapsack
```
```
 
```
```
    cout<<"Enter the no. of items ";
```
```
    cin>>n;
```
```
 
```
```
    int w[n];  //weight of items
```
```
    int p[n];  //value of items
```
```
 
```

    cout<<"Enter the weight and price of all items"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>w[i]>>p[i];
```
```
    }
```
```
 
```

    cout<<"enter the capacity of knapsack  ";

```
    cin>>M;
```
```
 
```

    cout<<"The maximum value of items that can be put into knapsack is "<<knapsack(w,p,n,M);

```
 
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to Solve 0 1 Knapsack Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```

int knapsack_dp(int n, int M, int w[], int p[])

```
{
```
```
    int i,j;
```
```
 
```

    //create a matrix to memoize the values using dynamic programming

```
    int knapsack[n+1][M+1];
```
```
 
```

    //knapsack[i][j] denotes the maximum attainable value of items in knpasack with i available

    //items and capacity of knapsack being j

```
 
```

    //initializing knapsack[0][j]=0 for 0<=j<=M

    //because if there is no item, no value can be attained

```
    for(j=0;j<=M;j++)
```
```
        knapsack[0][j]=0;
```
```
 
```

    //initializing knapsack[i][0]=0 for 0<=i<=n,

    //because in a bag of zero capacity, no item can be placed

```
    for(i=0;i<=n;i++)
```
```
        knapsack[i][0]=0;
```
```
 
```

    //now, filling the matrix in bottom up manner

```
    for(i=1;i<=n;i++)
```
```
    {
```
```
        for(j=1;j<=M;j++)
```
```
        {
```

            //check if the weight of current item i is less than or equal to the capacity of sack,

            //take maximum of once including the current item and once not including

```
            if(w[i-1]<=j)
```
```
            {
```

                knapsack[i][j]=max(knapsack[i-1][j],p[i-1]+knapsack[i-1][j-w[i-1]]);

```
            }
```
```
 
```

            //can not include the current item in this case

```
            else
```
```
            {
```

                knapsack[i][j]=knapsack[i-1][j];

```
            }
```
```
        }
```
```
    }
```
```
 
```
```
 
```
```
    return knapsack[n][M];
```
```
 
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,j;
```
```
    int n;  //number of items
```
```
    int M;  //capacity of knapsack
```
```
 
```
```
    cout<<"Enter the no. of items ";
```
```
    cin>>n;
```
```
 
```
```
    int w[n];  //weight of items
```
```
    int p[n];  //value of items
```
```
 
```

    cout<<"Enter the weight and price of all items"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>w[i]>>p[i];
```
```
    }
```
```
 
```

    cout<<"enter the capacity of knapsack  ";

```
    cin>>M;
```
```
 
```
```
 
```
```
    int result=knapsack_dp(n,M,w,p);
```
```
 
```

    //the maximum value will be given by knasack[n][M], ie. using n items with capacity M

    cout<<"The maximum value of items that can be put into knapsack is "<<result;

```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input number of items, weight & price of each item and the capacity of knapsack. We pass this values to the function knapsack_dp as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ knapsack.cpp
$ ./a.out
Enter the no. of items 4
Enter the weight and price of all items
2 3
3 4
4 5
5 6
enter the capacity of knapsack  5
The maximum value of items that can be put into knapsack is 7

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Building Bridges – Dynamic Programming Solutions

» Next - Integer Knapsack Problem – Dynamic Programming Solutions

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Programming MCQs
Practice Computer Science MCQs
Apply for Computer Science Internship
Apply for Information Technology Internship
Buy Programming Books

Recommended Articles: