#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int dp[10005],w[25]; int path[25][10005]; int main() { int m,n; while(cin>>m>>n) { memset(dp,0,sizeof(dp)); memset(path,0,sizeof(path)); memset(w,0,sizeof(w)); for(int i=1; i<=n; i++) cin>>w[i]; for(int i=n; i>=1; i--) { for(int j=m; j>=w[i]; j--) { if(dp[j-w[i]]+w[i]>dp[j]) { dp[j]=dp[j-w[i]]+w[i]; path[i][j]=1; } } } for(int i=1,j=m; i<=n; i++) { if(path[i][j]==1) { cout<<w[i]<<‘ ‘; j-=w[i]; } } cout<<"sum:"<<dp[m]<<endl; } return 0; }
原文：http://www.cnblogs.com/a-clown/p/5929965.html