思路：因为要按字典序输出答案，所以在进行 d p dp dp的时候优先选择较大的数，即先将数组从大到小排序，在状态转移，又因为要输出答案，所以需要用一个 v i s vis vis数组来维护答案。
#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #define pb push_back #include<cstring> using namespace std; const int N=1e4+5,M=205,inf=0x3f3f3f3f; int dp[M],n,m,a[N],vis[N][M]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1,greater<int>()); //贪心的重要一步 for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--) if(dp[j]<=dp[j-a[i]]+a[i]) vis[i][j]=1,dp[j]=dp[j-a[i]]+a[i]; if(dp[m]!=m) puts("No Solution"); else { vector<int>ans; int i=n; while(m>0){ if(vis[i][m]){ ans.pb(a[i]); m-=a[i]; } i--; } printf("%d",ans[0]); for(int i=1;i<ans.size();i++) printf(" %d",ans[i]); } }总结：子序列问题常常考虑 d p dp dp进行解决，本题关键在于如何将贪心与 d p dp dp进行结合。
