I'm trying to learn and implement the solution to 0/1 Knapsack Problem and I checked some videos and websites and I'm somewhat confused.
nitjsr.ac.in/faculty/courses ... roblem.pdf
youtube.com/watch?v=kH7weFvjLPY
However, when I tried to implement it, it didn't work. Please see my implementation (based on the algorithm outlined in the PDF given above):
int main()
{
int w[20], v[20], f[20][20], C, n, i=0, j=0;
cin>>n;
cin>>C;
for(i=0; i < n; i++) {
cout<<"Value: ";cin>>v[i]; cout<<endl;
cout<<"Weight: "; cin>>w[i]; cout<<endl;
}
for(i=0; i <= n; i++) {
for(j=0; j <= C; j++) {
if(i==0 || j == 0)
f[i][j]=0;
else if(w[i]<=j && i > 0)
{
f[i][j]=max(v[i]+f[i-1][j-w[i]], f[i-1][j]);
}
else
f[i][j]=f[i-1][j];
}
}
for(int i =0; i <= n; i++) {
for(int j=0; j <= C; j++) {
cout<<f[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Edit & Run
Unfortunately, this results in garbage values.
An alternate implementation which uses a different recurrence formula works geeksforgeeks.org/dynamic-pr ... k-problem/
What is the difference between the implementation given on GeeksForGeeks based on Wikipedia pseudocode and the implementation above?