L3-001. 凑零钱

题目链接：https://www.patest.cn/contests/gplt/L3-001

动态规划

这道题一看就知道应该用背包思想来做，不过想了好久没什么思路(dp实在是渣)，最后还是鼓捣出来了ac代码QAQ，细节加了注释。

代码如下：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<stack>
 5 using namespace std;
 6 const int INF=-0x3fffffff;
 7 stack<int>s;
 8 int dp[101],pre[101],a[10001];
 9 int main(void){
10     //freopen("in.txt","r",stdin);
11     for(int i=0;i<=100;++i){
12         dp[i]=INF;
13         pre[i]=-1;
14     }
15     dp[0]=0;
16     int n,m;
17     scanf("%d%d",&n,&m);
18     for(int i=1;i<=n;++i)
19         scanf("%d",&a[i]);
20     sort(&a[1],&a[1]+n);
21     for(int i=1;i<=n;++i){
22         for(int j=m;j>=a[i];--j){
23             if(dp[j]<=dp[j-a[i]]+1){
                /*加等号是因为在硬币个数相同的情况下，若其中一枚更大，相对另一枚更小，从而使得字典序最小*/
24                 dp[j]=dp[j-a[i]]+1;
25                 pre[j]=j-a[i];/*记录路径*/
26             }
27         }
28     }
29     if(dp[m]>0){
30         int k=m;
31         while(pre[k]){
32             s.push(k-pre[k]);
33             k=pre[k];
34         }
35         printf("%d",k);
36         while(!s.empty()){
37             printf(" %d",s.top());
38             s.pop();
39         }
40         printf("
");
41     }else printf("No Solution
");
42     return 0;
43 }

如有更好的方法，望不吝赐教!!