-2

Greeting everyone, I'm trying to solve 0/1 Knapsack problem using the Dynamic Programming Top-Down Approach. I'm pretty sure that most of my logic is correct, my code is compiling successfully. But, it's not giving the proper/correct output that is needed. For Instance, suppose weight[] has inputs as 10,20,30 and it's corresponding value[] has 60,100,120. The max weight that the Knapsack can hold onto is 50. The max profit should be 220, but my code is giving me the answer 280 instead. Please help me, here's my piece of code:-

#include<bits/stdc++.h>
using namespace std;

void knapsack(vector<int>& weight, vector<int>& value, int w, int n){
    
    vector<vector<int>> t;
    for(int i=0;i<n+1;++i){
        vector<int> temp;
        for(int j=0;j<w+1;++j){
                int x =0;
                temp.push_back(x);
        }
        t.push_back(temp);
        temp.clear();
    }
    
    for(int i=1;i<n+1;++i){
        for(int j=1;j<w+1;++j){
            if(weight[i-1]<=w){
                t[i][j] = max(value[i-1]+t[i-1][w-weight[i-1]], t[i-1][j]);
                
            }
            else{
               t[i][j] = t[i-1][j];
               
            }
        }
    }
    cout<<"Max Profit: "<<t[n][w];
   // return final;
   
//   vector<int> oneDimVector;
//  for(int i = 0; i < n+1; i++){
//      for(int j = 0; j < w+1; j++){
//         oneDimVector.push_back(t[i][j]);
//     }
//  }
//  vector<int>::iterator maxElement;
//  maxElement = max_element(oneDimVector.begin(), oneDimVector.end());
// cout<<"Max Profit: "<<*maxElement;
    
}

int main(){
    
    int n;
    int w;//Total weight of knapsack
    cin>>n;
    cin>>w;
    
    vector<int> weight;
    vector<int> value;
    
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        weight.push_back(x);
    }
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        value.push_back(x);
    }
    
  knapsack(weight,value,w,n);
}
4
  • 2
    Please don't use so-called "competition" or "online judge" sites to learn C++ or programming. That's not the purpose of such sites. All they seem to teach are very bad habits, and habits (good and bad) tend to stick so learning and using the bad ones will lead to bad code. Invest in some good C++ books and take classes. Sep 15, 2021 at 8:42
  • 1
    Please try to debug your code first before asking what's wrong with it. Debug my code-type questions are useful neither for other people nor for you.
    – Evg
    Sep 15, 2021 at 8:57
  • I'd recommend that you give your variables better names or add some comments. Do you think that if you looked at your own code in a year, you'd still know what w, n or t mean?
    – Aziuth
    Sep 15, 2021 at 9:47
  • Consider displaying your code on CodeReview. There is a lot that could be improved. For example, you start your code with a block that only initializes your storage, and this could be done by a readable one-liner instead (vector<vector<int>> t(n+1, vector<int>(w+1,0));). In that block, you create temp anew in each iteration despite it always being the same, and you call clear on it before you leave the scope in which it lives, which is pointless.
    – Aziuth
    Sep 15, 2021 at 9:50

1 Answer 1

1

I again debugged my code, I had to change one variable which I had written wrong in the following line of code:-

t[i][j] = max(value[i-1]+t[i-1][w-weight[i-1]], t[i-1][j]);

here, it should be:-

t[i][j] = max(value[i-1] + t[i-1][ j - weight[i-1]], t[i-1][j]);

Not the answer you're looking for? Browse other questions tagged or ask your own question.