01背包路径输出。
保证字典序最小：从大到小做背包。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<map> #include<stack> #include<queue> #include<string> #include<algorithm> using namespace std; const int maxn=100+10; bool dp[maxn*maxn][maxn]; int a[maxn*maxn]; int n,k; vector<int>ans; struct Path { int r,c; }p[maxn*maxn][maxn]; bool cmp(const int &a,const int &b) { return a>b; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n,cmp); memset(dp,0,sizeof dp); for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) p[i][j].r=p[i][j].c=-1; dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=k;j++) { if(dp[i-1][j]==0) continue; if(j+a[i]>k) continue; dp[i][j+a[i]]=1; p[i][j+a[i]].r=i-1; p[i][j+a[i]].c =j; } for(int j=0;j<=k;j++) { if(dp[i-1][j]==1&&dp[i][j]==0) { p[i][j].r=p[i-1][j].r; p[i][j].c=p[i-1][j].c; } dp[i][j]=max(dp[i][j],dp[i-1][j]); } } if(dp[n][k]==0) printf("No Solution "); else { int nowr=n,nowc=k; while(1) { ans.push_back(nowc-p[nowr][nowc].c); int tmpr=nowr,tmpc=nowc; nowc=p[tmpr][tmpc].c; nowr=p[tmpr][tmpc].r; if(nowc==0) break; } for(int i=0;i<ans.size();i++) { printf("%d",ans[i]); if(i<ans.size()-1) printf(" "); else printf(" "); } } return 0; }