一开始没多想，虽然注意到数据N<=10^4的范围，想PAT的应该不会超时吧，就理所当然地用dfs做了，结果最后一组真的超时了。
剪枝啥的还是过不了，就意识到肯定不是用dfs做了。
直到看到别人说用01背包的思路，果真好久没做题了智力水平下降，且原本dp就是我的弱项，压根就没把这题往dp上去想额。。。
(http://www.liuchuo.net/archives/2323)
题意：从n个硬皮中选取方案，使得总和价值正好为m，如果有多种，方案为排列最小的那个。
可以把硬币看成w=v(即容量=价值)的物品，现在要选取这些物品放入到容量为m的背包中，求能装的最大价值。
如果最大价值恰好等于容量m，那么方案则是可行的，否则输出No Solution。
由于要输出排列最小的方案，所以先将硬币按价值从大到小排列，相当于我先装大的，再装小的。
接着用01背包的方法求dp[j]。
chosen[i][j]数组表示背包里容量为j的时候，是否含有第i个物品，用于最后序列的输出。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=+;
const int maxv=;
int coins[maxn];
int dp[maxv]; //dp[v]表示：总和加起来=v的序列中最后一个值最小为多少。
int chosen[maxn][maxv];
int ans[maxn];
int cnt=; bool cmp(int a,int b){
return a>b;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<n;i++){
scanf("%d",&coins[i]);
}
sort(coins,coins+n,cmp); dp[]=;
for(int i=;i<n;i++){
for(int j=m;j>=coins[i];j--){
if(dp[j]<=dp[j-coins[i]]+coins[i]){
dp[j]=dp[j-coins[i]]+coins[i];
//printf("i:%d j:%d dp:%d chosen:%d\n",i,j,dp[j],coins[i]);
chosen[i][j]=;
}
}
}
if(dp[m]!=m){
printf("No Solution");
}
else{
int v=m,idx=n-;
while(v){
if(chosen[idx][v]){
ans[cnt++]=coins[idx];
v-=coins[idx];
}
idx--;
}
printf("%d",ans[]);
for(int i=;i<cnt;i++)
printf(" %d",ans[i]);
}
return ;
}
PS：想了解背包问题的，有个《背包九讲》，网上可以搜搜看看，挺好的