0 1 kanpsack

general
, ,
1

hey why is that my code gives wrong answer …:frowning:

//knapsack problem    
#include<cstdio>
#include<iostream>

int main()
{
    int t,a,j,i,k,l,W;
    printf("enter the amount of the items\n");
    scanf("%d",&t);
    int w[t+1],v[t+1];
    int b[t+1][t+1];
    printf("enter the total weight\n");
    scanf("%d",&W);        
    for(i=1;i<=t;i++)
    scanf("%d%d",&w[i],&v[i]);        
    for(i=0;i<=t;i++)
    {                         
        for(j=0;j<=W;j++)
        {                
            if((i==0)||(j==0))  b[i][j]=0;
            else if(w[i]<=j)
            {                
               if(b[i-1][j]>b[i-1][j-w[i]]+v[i])  b[i][j]=b[i-1][j];
               else b[i][j]=b[i-1][j-w[i]]+v[i];
            }
            else if(w[i]>j) b[i][j]=b[i-1][j];              
        }
    }
    printf("the max value is %d\n",b[t][W]);
    system("pause");
}

        

eg- for 3 itmes the folowong is the weight and values.
(weight,value)- 
(3       ,5)
(2,       3)
(1 ,      4)
     the max value should be 9
but i am getting 4. PLZZZZ do help unable to figure it out.
2

int b[t+1][t+1]; should be changed to int b[t+1][W+1]; . You can check your code here .

1 Like
3

thnx…:)…