【PAT甲级】1068 Find More Coins (30 分)（背包/DP）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int a[10007];
 5 int dp[107];
 6 int vis[10007][107];
 7 int main(){
 8     ios::sync_with_stdio(false);
 9     cin.tie(NULL);
10     cout.tie(NULL);
11     int n,m;
12     cin>>n>>m;
13     for(int i=1;i<=n;++i)
14         cin>>a[i];
15     sort(a+1,a+1+n);
16     for(int i=n;i;--i)
17         for(int j=m;j>=a[i];--j)
18             if(dp[j]<=dp[j-a[i]]+a[i]){
19                 dp[j]=dp[j-a[i]]+a[i];
20                 vis[i][j]=1;
21             }
22     if(dp[m]<m)
23         cout<<"No Solution";
24     else{
25         int i=1,j=m;
26         while(1){
27             if(vis[i][j]){
28                 cout<<a[i];
29                 j-=a[i];
30                 if(j)
31                     cout<<" ";
32             }
33             ++i;
34             if(!j)
35                 break;
36         }
37     }
38     return 0;
39 }