Integer Knapsack Problem - Dynamic Programming Solutions

This is a C++ Program that Solves Integer 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- there are infinite instances of each item available. So, any item can be selected any number of times.

The problem is similar to 0 1 knapsack problem. The only difference is that in 0 1 knapsack problem a particular item could be put into knapsack at most one time. But in integer knapsack problem, there is no such limit.

Problem Solution

This problem can be solved using bottom up DP. We will first calculate the maximum attainable value in knapsack with duplicate items permitted with a capacity of 1. Then, we will tabulate this value and use this value to calculate the maximum value for capacity 2. Similarly, we will calculate the required value.
While calculating the maximum value of a particular capacity, we will consider every item and will select the one which results in giving the maximum value.

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

Expected Input and Output

Case-1:

 
number of items, n=3
 
weight of items, w[]=4 8 2
value of items,  v[]=7 8 3
 
capacity of knapsack, M=11
 
maximum attainable value of items=17
by collecting first item twice and third item once

Case-2:

 
n=3
w[]=3 8 6
v[]=7 8 4
 
M=10

Case-3:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
maximum attainable value of items=21 
by collecting first item 3 times
 
n=4
w[]=3  6  2 4
v[]=14 30 9 19
 
M=10
 
maximum attainable value of items=49

Program/Source Code

Here is source code of the C++ Program to Solve Integer 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 integer_knapsack(int n, int M, int w[], int p[])

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

    //create a vector of size M+1 to memoize calculated values

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

    //knapsack[i] denotes the maximum possible attainable value with capacity of knapsack being i

    //since no item can be put in a knapsack of capacity zero

```
    knapsack[0]=0;
```
```
 
```

    //the vector will be filled sequentially first calculating value of knapsack[1]

    //then using this value to calculate knapsack[2] and so on.

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

        //the value of knapsack[i] will be greater than or equal to knapsack[i-1]

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

        //try to put every item one by one

        //and select the one that gives maximum value

```
        for(j=0;j<n;j++)
```
```
        {
```

            //if this item can fit in the knapsack

```
            if(i>=w[j])
```
```
            {
```

                //this is a temporary value

                //if this value is greater than the current value of knapsack[i], this value will replace the value of knapsack[i]

                tempValue=p[j]+knapsack[i-w[j]];

```
 
```

                //replace the value of knapsack[i] with tempValue

                if(tempValue>knapsack[i])

```
                {
```

                    knapsack[i]=tempValue;

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

    //maximum attainable value with duplicate items permitted in knapsack of capacity M

```
    return knapsack[M];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```
```
    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=integer_knapsack(n,M,w,p);

```
 
```

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

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

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

Runtime Test Cases

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

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

« Prev - 0-1 Knapsack Problem using Dynamic Programming

» Next - Treats for the Cows – Dynamic Programming Solutions

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Practice Computer Science MCQs
Practice Programming MCQs
Check Computer Science Books

Recommended Articles: