WA in MARCHA1 ??

general
1

i have applied knapsack algorithm on notes >>
it is working for all test cases …

here is my code >>


   
   #include<iostream>
    #include<algorithm>
    #define max(a,b) (a>b)?a:b
    using namespace std;
    int main()
    {
    int t,non,amount;
    scanf("%d",&t);
    while(t--)
    {
    scanf("%d %d",&non,&amount);
    int arr[non+1],i,w;
    for(i=1;i<=non;i++)
    {
    scanf("%d",&arr[i]);
    }
    sort(arr,arr+non);
    
    int V[non+1][amount+1];
    
    for(w=0;w<=amount;w++)
        V[0][w]=0;
    for(w=0;w<=non;w++)
        V[w][0]=0;
        
        
    for(i=1;i<=non;i++)
        for(w=1;w<=amount;w++)
    {
        if(arr[i]<=w)  //weight of this item is less than the sub problem weight
            {V[i][w]=max(V[i-1][w],arr[i]+V[i-1][w-arr[i]]);}
        else
            {V[i][w]=V[i-1][w];}
        
        
    }
    
 
    
    if(V[non][amount] == amount)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    }
    return 0;
    }
2

Consider the test case :
1 (number of test cases )
3 6 (values of n and m )
1 2 2 3 ( the actual note values )
Your code gives answer “No” , while it is possible to make 6 = 1 + 2 + 3 , so answer is “Yes” .
You should keep your double array V as boolean double array and let V[i][j] denote whether it is possible to make j amount using first i notes . Then V[i][j] = V[i-1][j] OR V[i-1][j-arr[i]] . ( Note “OR” denotes logical “OR” of two booleans ) .
Also it is not necessary to sort the array in this approach .

3

my code is giving correct answer for :
1
4 6
1
2
2
3

Plz tell me another test case ??

4

Am really sorry , I put the wrong value of n in the test case which made your code fail . Anyway you can still use the “boolean” suggestion . However if you want a test case to determine why your current code is giving WA , I will try to generate one , give me some time .

5

ok sir …