1 / 2
Nov 2014

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.pdf1
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/3

What is the difference between the implementation given on GeeksForGeeks based on Wikipedia pseudocode and the implementation above?

  • created

    Nov '14
  • last reply

    Nov '14
  • 1

    reply

  • 371

    views

  • 1

    user

  • 3

    links

Problem solved! Actually I was using 0-based indexing for v[] and w[] arrays and 1-based indexing during actual computation!

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 14 6d

Want to read more? Browse other topics in C and C++ or view latest topics.