-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);
}
Parth Arora
  • 21
  • 7
  • 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](https://stackoverflow.com/a/388282/440558) and take classes. – Some programmer dude Sep 15 '21 at 08: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 '21 at 08: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 '21 at 09:47
  • Consider displaying your code on [CodeReview](https://codereview.stackexchange.com/). 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> t(n+1, vector(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 '21 at 09:50

1 Answers1

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]);
Parth Arora
  • 21
  • 7