This is a C++ Program that Solves Integer Knapsack Problem using Dynamic Programming technique.
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.
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).
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
n=3 w=3 8 6 v=7 8 4 M=10
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
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.
using namespace std;
int integer_knapsack(int n, int M, int w, int p)
//create a vector of size M+1 to memoize calculated values
//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
//the vector will be filled sequentially first calculating value of knapsack
//then using this value to calculate knapsack and so on.
//the value of knapsack[i] will be greater than or equal to knapsack[i-1]
//try to put every item one by one
//and select the one that gives maximum value
//if this item can fit in the knapsack
//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]
//replace the value of knapsack[i] with tempValue
//maximum attainable value with duplicate items permitted in knapsack of capacity M
int n; //number of items
int M; //capacity of knapsack
cout<<"Enter the no. of items ";
int w[n]; //weight of items
int p[n]; //value of items
cout<<"Enter the weight and price of all items"<<endl;
cout<<"enter the capacity of knapsack ";
cout<<"The maximum value of items that can be put into knapsack is "<<result;
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.
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.