fork(20) download
  1. #include<iostream>
  2. #define max(a,b) (a>b)?a:b
  3. using namespace std;
  4. int main()
  5. {
  6. int t,non,amount;
  7. scanf("%d",&t);
  8. while(t--)
  9. {
  10. scanf("%d %d",&non,&amount);
  11. int arr[non+1],i,w;
  12. for(i=1;i<=non;i++)
  13. {
  14. scanf("%d",&arr[i]);
  15. }
  16.  
  17. int V[non+1][amount+1];
  18. for(w=0;w<=amount;w++)
  19. V[0][w]=0;
  20. for(w=0;w<=non;w++)
  21. V[w][0]=0;
  22. for(i=1;i<=non;i++)
  23. for(w=1;w<=amount;w++)
  24. {
  25. if(arr[i]<=w) //weight of this item is less than the sub problem weight
  26. {V[i][w]=max(V[i-1][w],arr[i]+V[i-1][w-arr[i]]);}
  27. else
  28. {V[i][w]=V[i-1][w];}
  29. }
  30.  
  31. if(V[non][amount] == amount)
  32. cout<<"Yes"<<endl;
  33. else
  34. cout<<"No"<<endl;
  35. }
  36. return 0;
  37. }
Success #stdin #stdout 0.02s 2728KB
stdin
1
4 6
1
2
2 
3
stdout
Yes