多重背包记录路径：记录路径就是从后往前看每个状态是由哪个状态转移过来的。 链接：http://icpc.upc.edu.cn/problem.php?cid=2590&pid=6
#include <iostream> #include <string.h> using namespace std; const int N=2010; int cnt[N]; int n,W; int w[N],v[N]; int dp[N][N]; int main() { int m,n; while(scanf("%d%d",&m,&n)!=EOF) { memset(cnt,0,sizeof cnt); memset(dp,0x3f,sizeof dp); for(int i=0;i<=n+1;i++) dp[i][0]=0; for(int i=1;i<=n;i++) { scanf("%d",&v[i]); w[i]=1; } for(int i=n; i>=1; i--) for(int j=1; j<=m; j++) { for(int k=0; k*v[i]<=j; k++) dp[i][j]=min(dp[i][j],dp[i+1][j-k*v[i]]+k*w[i]); } int j=m; for (int i=1;i<=n;i++) { //不能这么记录因为dp[n+1]没有更新 // while(j>=v[i]&&dp[i][j]==dp[i+1][j-v[i]]+w[i]) // { // cnt[i]++; // j-=v[i]; // } for(int k=j/v[i]; k>=0; k--) { if(dp[i][j]==dp[i+1][j-k*v[i]]+k*w[i]) { cnt[i]+=k;j-=k*v[i];break; } } } if(dp[1][m]>=0x3f3f3f3f) printf("-1\n"); else { for(int i=1;i<=n;i++) { printf("%d ",cnt[i]); } printf("\n"); } } }