韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。
输入样例1：
8 9 5 9 8 7 2 3 4 1 输出样例1： 1 3 5 输入样例2： 4 8 7 2 4 3 输出样例2：No Solution
PS ：及判断是否能够装满背包，能的话输出装的物品的价值序列。我们可以用一个pre[]记录当前状态由那个转移而来，另一个记录当前状态的价值。 （背包&路径记录） #include<map> #include<queue> #include<cmath> #include<cstdio> #include<stack> #include<iostream> #include<cstring> #include<algorithm> #define LL int #define inf 0x3f3f3f3f #define eps 1e-8 #include<vector> #define ls l,mid,rt<<1 #define rs mid+1,r,rt<<1|1 #define LL __int64 using namespace std; int arr[10100],dp[10100],val[10100],pre[10100]; void dfs(int u){ if(!pre[u]){ printf("%d",val[u]);return ; } dfs(pre[u]); printf(" %d",val[u]); } int main(){ int n,m,j,i,k; while(~scanf("%d%d",&n,&m)){ for(i = 0;i < n;++ i){ scanf("%d",&arr[i]); } sort(arr,arr+n); memset(dp,-inf,sizeof(dp)); memset(pre,-1,sizeof(pre)); dp[0] = 0; for(i = 0;i < n;++ i){ for(j = m;j >= arr[i];-- j){ if(dp[j] <= dp[j-arr[i] ]+1){ dp[j] = dp[j-arr[i] ]+1; pre[j] = j - arr[i]; val[j] = arr[i]; } } } if(dp[m]>0){ dfs(m);puts(""); } else puts("No Solution"); } return 0; } #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> #include <set> #include <stack> #include <map> #include <climits> using namespace std; #define LL long long const int INF=0x3f3f3f3f; int a[10005]; int n,m,ans[10005]; int flag,cnt; void dfs(int k,int sum1,int sum2) { if(sum1==m) {flag=1;ans[cnt++]=k;return;} if(sum1+sum2<m||k>=n) return; if(sum1+a[k]<=m) { dfs(k+1,sum1+a[k],sum2-a[k]); if(flag) {ans[cnt++]=k;return ;} dfs(k+1,sum1,sum2-a[k]); if(flag) return ; } else return ; } int main() { while(~scanf("%d %d",&n,&m)) { int sum=0; for(int i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } sort(a,a+n); cnt=flag=0; dfs(0,0,sum); if(flag) { printf("%d",a[ans[cnt-1]]); for(int i=cnt-2;i>0;i--) printf(" %d",a[ans[i]]); printf("\n"); } else printf("No Solution\n"); } return 0; }