Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int knapsack(int n,int max1,int val[])
- {
- int arr[n+1][max1+1];
- for(int i=0;i<=max1;i++)
- arr[0][i]=0;
- for(int i=0;i<=n;i++)
- arr[i][0]=1;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=max1;j++)
- {
- if(val[i-1]>j)
- arr[i][j]=arr[i-1][j];
- else
- arr[i][j]=arr[i-1][j]+arr[i][j-val[i-1]];
- }
- }
- cout<<arr[n][max1]<<endl;
- // for(int i=0;i<=n;i++)
- // {
- // for(int j=0;j<=max1;j++)
- // {
- // cout<<arr[i][j]<<" ";
- // }
- // cout<<endl;
- // }
- }
- int main()
- {
- int t,n,x,M;
- cin>>t;
- while(t--)
- {
- cin>>n;
- int val[n],wt[n];
- for(int i=0;i<n;i++)
- cin>>val[i];
- sort(val,val+n);
- cin>>M;
- knapsack(n,M,val);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement