动态规划，用dp[i][j]记录当使用前i个硬币时是否可以达到价值j，可以则为1，反之为0；
用pre[i][j]记录当前第i个硬币是否在状态dp[i][j]中使用，是则为1，反之为0；
最后在寻找解时，如果pre[i][j]为1，则记录到ans（便于一起输出），反之则不断i--，则到pre[i][j]为1。
先对数据进行从大到小排序，保证最后的输出是smaller的，用下面的例子能更好的说明算法的思想。
input info 4 9 1 3 4 5 dp[i][j] info 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 pre[i][j] info 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 result info 1 3 5
#include<stdio.h>
#include<stdlib.h>
int cmp(const void* ta,const void* tb){
int* a=(int*)ta;
int* b=(int*)tb;
return *a<*b;
}
int dp[10001][101],pre[10001][101];
int arr[10001],ans[10001];
int main(){
int i,j,n,m;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
qsort(arr+1,n,sizeof(int),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;
}