题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805402305150976

    经验

    1. 输入可以从1开始 for(int i = 1; i <= n; i++)
    2. 最优路径的记录方法
    3. 第19行之所以是小于等于号，因为原来第数组首先是从大到小，倒序的时候就满足从小到大的字典序，若出现相等，那么为了保证字典序最小（因为如果后面还有方案的话一定是字典序大于当前方案的）就要选择当前的硬币
    4. 大于的情况下，之所以else没有对dp[v]修改是因为这个时候就等于自己
    1. #include<algorithm>
    2. #include<cstdio>
    3. using namespace std;
    5. const int maxn = 10010;
    6. int coin[maxn], dp[maxn], choice[maxn][maxn];
    7. bool flag[maxn];
    8. bool cmp(int a, int b){
    9.     return a > b;
    10. }
    11. int main(){
    12.     int n, m;
    13.     scanf("%d%d", &n, &m);
    14.     for(int i = 1; i <= n; i++) scanf("%d", &coin[i]);
    15.     sort(coin + 1, coin + n + 1, cmp);
    16.     //for(int i = 0; i < n; i++) dp[i] = 0;
    17.     for(int i = 1; i <= n; i++){
    18.         for(int c = m; c >= coin[i]; c--){
    19.             if(dp[c] <= dp[c - coin[i]] + coin[i]){//价值等于重量
    20.                 dp[c] = dp[c - coin[i]] + coin[i];
    21.                 choice[i][c] = 1;
    22.             } else choice[i][c] = 0;
    23.         }
    24.     }
    25.     if (dp[m] != m) printf("No Solution\n");
    26.     else {
    27.         int num = 0, c = m;
    28.         for(int k = n; k >= 0; k--){
    29.             if(choice[k][c] == 1){
    30.                 flag[k] = true;
    31.                 c -= coin[k];
    32.                 num++;
    33.             }
    34.         }
    35.         for(int i = n; i >= 1; i--){
    36.             if(flag[i] == true){
    37.                 printf("%d", coin[i]);
    38.                 num--;
    39.                 if(num != 0) printf(" ");
    40.             }
    41.         }
    42.     }
    43.     return 0;
    44. }