题目:http://pat.zju.edu.cn/contests/pat-a-practise/1068
题解:
背包。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff int dp[10005][105]; //dp[i][j]=max(dp[i-1][j],dp[i-1][j-num[i]]+num[i]) //dp[i][j]表示不超过j且从前i个硬币中挑选出的最大和 int num[10005]; bool flag[10005][105]; int main() { int n,m; memset(flag,false,sizeof(flag)); memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",num+i); sort(num+1,num+1+n,greater<int>()); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { if(j<num[i]||dp[i-1][j-num[i]]+num[i]<dp[i-1][j]) dp[i][j]=dp[i-1][j]; else { dp[i][j]=dp[i-1][j-num[i]]+num[i]; flag[i][j]=true; } } if(dp[n][m]!=m) { printf("No Solution"); } else { bool first=true; for(int i=n;i>=1&&m>0;--i) { if(flag[i][m]) { if(first) { printf("%d",num[i]); first=false; } else printf(" %d",num[i]); m-=num[i]; } } } printf("\n"); return 0; }