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


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


w[]=3 8 6
v[]=7 8 4


Participate in Data Structure I Certification Contest of the Month Now!
maximum attainable value of items=21 
by collecting first item 3 times
w[]=3  6  2 4
v[]=14 30 9 19
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.

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int integer_knapsack(int n, int M, int w[], int p[])
  5. {
  6.     int i,j;
  7.     int tempValue;    
  9.     //create a vector of size M+1 to memoize calculated values
  10.     int knapsack[M+1];
  12.     //knapsack[i] denotes the maximum possible attainable value with capacity of knapsack being i
  13.     //since no item can be put in a knapsack of capacity zero
  14.     knapsack[0]=0;
  16.     //the vector will be filled sequentially first calculating value of knapsack[1]
  17.     //then using this value to calculate knapsack[2] and so on.
  18.     for(i=1;i<=M;i++)
  19.     {
  20.         //the value of knapsack[i] will be greater than or equal to knapsack[i-1]
  21.         knapsack[i]=knapsack[i-1];
  23.         //try to put every item one by one 
  24.         //and select the one that gives maximum value 
  25.         for(j=0;j<n;j++)
  26.         {
  27.             //if this item can fit in the knapsack
  28.             if(i>=w[j])
  29.             {
  30.                 //this is a temporary value
  31.                 //if this value is greater than the current value of knapsack[i], this value will replace the value of knapsack[i]
  32.                 tempValue=p[j]+knapsack[i-w[j]];
  34.                 //replace the value of knapsack[i] with tempValue
  35.                 if(tempValue>knapsack[i])
  36.                 {
  37.                     knapsack[i]=tempValue;
  38.                 }
  39.             }
  41.         }
  42.     }
  44.     //maximum attainable value with duplicate items permitted in knapsack of capacity M
  45.     return knapsack[M];
  46. }
  48. int main()
  49. {
  50.     int i;
  51.     int n;  //number of items
  52.     int M;  //capacity of knapsack
  54.     cout<<"Enter the no. of items ";
  55.     cin>>n;
  57.     int w[n];  //weight of items
  58.     int p[n];  //value of items
  60.     cout<<"Enter the weight and price of all items"<<endl;
  61.     for(i=0;i<n;i++)
  62.     {
  63.         cin>>w[i]>>p[i];
  64.     }
  66.     cout<<"enter the capacity of knapsack  ";
  67.     cin>>M;
  69.     int result=integer_knapsack(n,M,w,p);
  71.     cout<<"The maximum value of items that can be put into knapsack is "<<result;
  73.     cout<<endl;
  74.     return 0;
  75. }
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
$ 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.


Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.