c++ - Unexpected answer for 0-1 knapsack -

my code 0-1 knapsack:

#include <iostream> #include <sstream> using namespace std;  int max(int a,int b) {     return a>b?a:b; } int main() {     string s;     int n,w;      getline(cin,s);     stringstream(s)>>n>>w;      cout<<"enter value , weight of item\n";     int v[n+1],w[n+1];      for(int i=1;i<=n;i++)     {         getline(cin,s);         stringstream(s)>>v[i]>>w[i];     }     int max_val[n+1][w+1];     for(int i=0;i<=w;i++)     {         for(int j=0;j<=n;j++)         {             if(i==0 || j==0)             {                 max_val[i][j]=0;             }             else             {                 max_val[i][j]=max_val[i][j-1];                 if(w[j]<=i)                 {                     max_val[i][j]=max(max_val[i][j],max_val[i-w[j]][j-1]+v[j]);                 }             }             cout<<max_val[i][j]<<" ";         }         cout<<"\n";     }     cout<<max_val[w][n]; } 

input:

3 5   60 1   100 2   120 3   

max_val:

0 0 0 0    0 60 60 60    0 60 100 100    0 60 160 160    0 60 160 180    0 60 160 160    

the output 160 expected output 220.
value matrix 60,100,120 , weight 1,2,3.
when debugged value of weight matrix changed during i=5 gave wrong answer.
can tell me why weight matrix getting modified?

you have defined max_val array int max_val[n+1][w+1], first index number of item, , second weight. however, use indices in opposite order: max_val[i][j] i being weight , j item number.

therefore writes max_val out-of-bound, , can happen. simplest way fix change max_val declaration int max_val[w+1][n+1].