So... I have a code that's not working for the 1-0 knapsack problem (it's supposed to give me the greatest value you can get, not the items themselves), please find it.
/*
problem description:
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.
*/
#include <iostream>
using namespace std;
struct obj{
int value;
int weight;
}; //object struct describing the object with a value and a weight
int main(void){
int i,j,kw,objs,val,left;
cout<<"knapsack max weight: ";
cin>>kw;
cout<<"number of objects: ";
cin>>objs;
obj object[objs];
for(i=1;i<=objs;i++){
cout<<"object "<<i<<":"<<endl;
cout<<"value: ";
cin>>object[i].value;
cout<<"weight: ";
cin>>object[i].weight;
cout<<endl;
}
//Until here I just initiated variables and wrote down the reading functions stuff
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
bool keep[kw][objs]; //You shouldn't care about this matrix
for(i=0;i<=objs;i++)
matrix[0][i]=0;
for(i=0;i<=kw;i++)
matrix[i][0]=0;
//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
for(i=1;i<=objs;i++){
for(j=1;j<=kw;j++){
if(object[j].weight>i){ //If the object is heavier, the obvious solution is the knapsack problem with less objects
keep[i][j]=0;
matrix[i][j]=matrix[i-1][j];
}
else{
left=kw-object[i].weight;
val=object[i].weight+matrix[i-1][left]; //Once you put an object in you have left space left and i-1 objects left, this is another knapsack problem, so you add its result and get the optimal matrix[i][j] value
if(val>matrix[i-1][j]){ //If the solution is better than the one with fewer objects, use that solution instead
keep[i][j]=1;
matrix[i][j]=val;
}
else{ //If not, use the i objects solution instead
keep[i][j]=0;
matrix[i][j]=matrix[i-1][j];
}
}
}
}
cout<<"RESULT: "<<matrix[objs][kw]<<endl; //outputs the result
return 0;
}
Yes, I am a begginer in computer science, the excuse is that I'm in middle school...
