fork download
copy 
  1. /*
  2. problem description:
  3. you have a knapsack with a maximum capacity kw and a number of objects objs with a value and weight. If you put and object in the knapsack it's already in the knapsack and you can't add the object again in it. What is the highest added value of the objects you can get while the added weight of the objects is not greater than the maximum capacity.
  4. */
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. struct obj{
  9.     int value;
  10.     int weight;
  11. }; //object struct describing the object with a value and a weight
  12.  
  13. int main(void){
  14.     int i,j,kw,objs,val,left;
  15.     cout<<"knapsack max weight: ";
  16.     cin>>kw;
  17.     cout<<"number of objects: ";
  18.     cin>>objs;
  19.     obj object[objs];
  20.     for(i=1;i<=objs;i++){
  21.         cout<<"object "<<i<<":"<<endl;
  22.         cout<<"value: ";
  23.         cin>>object[i].value;
  24.         cout<<"weight: ";
  25.         cin>>object[i].weight;
  26.         cout<<endl;
  27.     }
  28.     //Until here I just initiated variables and wrote down the reading functions stuff
  29.     int matrix[kw][objs]; //This matrix should contain the all the knapsack problems with the max capacity smaller and equal to kw and the number of objects smaller or equal to objs
  30.     bool keep[kw][objs]; //You shouldn't care about this matrix
  31.     for(i=0;i<=objs;i++)
  32.         matrix[0][i]=0;
  33.     for(i=0;i<=kw;i++)
  34.         matrix[i][0]=0;
  35.     //In dynamic programming you need a base case so i setted all the knapsack cases with kw=0 and the number of objs=0 to zero
  36.     for(i=1;i<=objs;i++){
  37.         for(j=1;j<=kw;j++){
  38.             if(object[j].weight>i){ //If the object is heavier, take previous rows value at current weight
  39.                 keep[i][j]=0;
  40.                 matrix[i][j]=matrix[i-1][j];
  41.             }
  42.             else{
  43.                 if((object[i].value + matrix[i-1][kw - object[i].weight]) > matrix[i-1][j]){
  44.                 	// if current value + value @ [previous row, remaining weight] > previous rows value at this weight
  45.                 	matrix[i][j] = object[i].value + matrix[i-1][kw-object[i].weight];
  46.                 }
  47.                 else {
  48.                 	matrix[i][j] = matrix[i-1][j];
  49.                 }
  50.                 /*left=kw-j;
  51.                 val=object[i].weight+matrix[i-1][left];
  52.                 if(val>matrix[i-1][j]){ //If the solution is better than the one with fewer objects, use that solution instead
  53.                     keep[i][j]=1;
  54.                     matrix[i][j]=val;
  55.                 }
  56.                 else{ //If not, use the i objects solution instead
  57.                     keep[i][j]=0;
  58.                     matrix[i][j]=matrix[i-1][j];
  59.                 }*/
  60.             }
  61.         }
  62.     }
  63.     cout<<"RESULT: "<<matrix[objs][kw]<<endl; //outputs the result
  64.     return 0;
  65. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
5
6
2
1
3
1
5
5
4
1
2
1
3
1
stdout
copy 
knapsack max weight: number of objects: object 1:
value: weight: 
object 2:
value: weight: 
object 3:
value: weight: 
object 4:
value: weight: 
object 5:
value: weight: 
object 6:
value: weight: 
RESULT: 14
https://ideone.com/PMfa6w
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!