fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<int>v;
  4. double o_1_knapsack(int k, int w[], int p[], int n){
  5.     int mat[n+1][k+1];
  6.     for(int i = 0; i <= n; i++){
  7.         for(int j = 0; j <= k; j++){
  8.             if(i ==0 || j == 0){
  9.                 mat[i][j] = 0;
  10.             }
  11.             else if(w[i-1]<=j){
  12.                 mat[i][j] = max(p[i-1]+mat[i-1][j-w[i-1]], mat[i-1][j]);
  13.             }
  14.             else{
  15.                 mat[i][j] = mat[i-1][j];
  16.             }
  17.         }
  18.     }
  19.     int i = n;
  20.     int j = k;
  21.     while(i>0 && j>0){
  22.         if(mat[i][j] == mat[i-1][j]){
  23.             i--;
  24.         }
  25.         else{
  26.             v.push_back(i);
  27.             i--;
  28.             j=j-w[i-1];
  29.         }
  30.     }
  31.     return mat[n][k];
  32. }
  33.  
  34.  
  35. int main(){
  36. int knapsack = 7;
  37. int weight[]= {2,3,1,2,4};
  38. int profit[]= {7,12,5,12,15};
  39. int n = sizeof(weight)/sizeof(weight[0]);
  40. double ans = o_1_knapsack(knapsack,weight,profit,n);
  41. cout<<ans<<endl;
  42. for(int i = 0; i <v.size(); i++){
  43.     cout<<"item: "<<v[i]<<endl;
  44. }
  45. return 0;
  46. }
  47.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
32
item: 5
item: 4
item: 3
https://ideone.com/QcvVHF
language:
C++ (gcc 8.3)
created:
2 days 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!