Knapsack Conceptual Doubt - Dynamic Programming
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.
http://www.nitjsr.ac.in/faculty/courses/CA03_2_0-1%20Knapsack%20Problem.pdf
https://www.youtube.com/watch?v=kH7weFvjLPY
However, when I tried to implement it, it didn't work. Please see my implementation below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
#include <iostream>
using namespace std;
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;
}
|
An alternate implementation which uses a different recurrence formula works
http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
What is the difference between the implementation given on GeeksForGeeks based on Wikipedia pseudocode and the implementation above?
Topic archived. No new replies allowed.