# WA in MARCHA1 ??

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;
}

``````

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 .

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

Plz tell me another test case ??

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 .

ok sir …

//