fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int noOfItems, items[100], maxWeight, maxItems, value[100];
  6. int dp[100][1000][100];
  7.  
  8. int solve(int idx, int currentWeight, int itemsLeft){
  9.     if(idx == noOfItems || itemsLeft == 0) return 0;
  10.     if(dp[idx][currentWeight][itemsLeft] != -1) return dp[idx][currentWeight][itemsLeft];
  11.     int v1 = 0, v2 = 0;
  12.     //try to included the current item
  13.     if(currentWeight >= items[idx]) v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1) + value[idx];
  14.     //exclude current item
  15.     v2 = solve(idx+1, currentWeight, itemsLeft);
  16.     return dp[idx][currentWeight][itemsLeft] = max(v1, v2);
  17. }
  18.  
  19. //print the contents of the knapsack
  20. void print(int idx, int currentWeight, int itemsLeft){
  21.     if(idx == noOfItems || itemsLeft == 0) return;
  22.     int v1 = 0, v2 = 0;
  23.     if(currentWeight >= items[idx]) v1 = solve(idx+1, currentWeight-items[idx], itemsLeft-1) + value[idx];
  24.     v2 = solve(idx+1, currentWeight, itemsLeft);
  25.     if(v1 >= v2){
  26.         cout << idx << " " << items[idx] << " " << value[idx] << endl;
  27.         print(idx+1, currentWeight-items[idx], itemsLeft-1);
  28.         return;
  29.     }else{
  30.         print(idx+1, currentWeight, itemsLeft);
  31.         return;
  32.     }
  33. }
  34.  
  35. int main(){
  36.     cin >> noOfItems >> maxWeight >> maxItems;
  37.     for(int i = 0;i < noOfItems;i++) cin >> items[i] >> value[i];
  38.     memset(dp, -1, sizeof dp);
  39.     cout << solve(0, maxWeight, maxItems) << endl;  //prints the maximum value that we can get from the constraints
  40.     cout << "Printing the elements in the knapsack" << endl;
  41.     print(0, maxWeight, maxItems);
  42. return 0;
  43. }
  44.  
  45. /*
  46. sample Input :
  47. 5 15 3
  48. 4 6
  49. 3 4
  50. 5 5
  51. 7 3
  52. 7 7
  53. */
  54.  
Success #stdin #stdout 0.05s 42528KB
comments (?)
stdin
copy 
5 15 3
4 6
3 4
5 5
7 3
7 7
stdout
copy 
17
Printing the elements in the knapsack
0 4 6
1 3 4
4 7 7
https://ideone.com/wKzqXk
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!