3648 - 硬币支付
伊娃喜欢从宇宙的各个角落收集硬币，其中包括一些其它的行星像火星。有一天，她参观了环球购物中心可以接
受各种硬币支付。然而，有了付款的特殊要求：每个账单，她必须支付的确切数额。因为她有多达104个硬币
她，她肯定需要你的帮助。你应该告诉她，对于任何给定的数量的钱，她是否可以找到一些硬币付钱。
Input
每个输入文件包含一个测试用例。对于每一种情况下，第一行包含2个正数：n（＜＝104，硬币的总数）和
M（＜＝102，钱伊娃金额支付）。第二行包含n个硬币的面值，都是正数。在一行中的所有数字用一个空格隔
开。
Output
对于每个测试案例，在一行打印面值V1 < V2 <= =…＜＝VK，V1 + V2 +…+ VK = M的所有数字必须用一个空格隔开，而且最后
一排没有多余的空间。如果这样的解不唯一，输出最小的序列。如果没有解决方案，输出“无解”代替。
注：序列{ A[1]，A[2]，……}被称为比序列{ B [ 1 ]，B [ 2 ]，……}小如果存在K＞＝1，A[i]=B [i],对于所有i< K，a[ k ] < B [K
]。
Examples
Input
8 9 5 9 8 7 2 3 4 1 4 8 7 2 4 3
Output
1 3 5 No Solution
Solution C++
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int cmp(int a,int b){ return a > b; } int dp[10001][101],pre[10001][101]; int arr[10001],ans[10001]; int main(){ int i,j,n,m; while(scanf("%d %d",&n,&m)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&arr[i]); } sort(arr + 1, arr + n + 1,cmp); for(i=0;i<=n;i++){ for(j=0;j<=m;j++){ dp[i][j]=0; pre[i][j]=0; } } for(i=0;i<=n;i++){ dp[i][0]=1; } for(i=1;i<=n;i++){ for(j=arr[i];j<=m;j++){ if(dp[i-1][j-arr[i]]){ dp[i][j]=1; pre[i][j]=1; } else{ dp[i][j]=dp[i-1][j]; } } } if(!dp[n][m]){ printf("No Solution\n"); } else{ int cnt=0; while(n>0){ if(pre[n][m]){ ans[cnt]=arr[n]; m=m-arr[n]; n=n-1; cnt++; } else{ n--; } } for(i=0;i<cnt-1;i++){ printf("%d ",ans[i]); } printf("%d\n",ans[cnt-1]); } } return 0; }