本文共 937 字，大约阅读时间需要 3 分钟。
地址：
题意：背包问题，最多装多少。
mark：本题要求输出装的每一个价值，需要回溯一下，必须用二维的。
代码：
#include #include #include #include #include #include #include #define LL long longusing namespace std;const int N = 10010;int n,vv;int v[30];int dp[30][N];int max(int a, int b) { return a > b ? a : b;}void zero_dp(int i){ for(int j = vv; j >= 0; j--) { dp[i][j] = dp[i-1][j]; if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+v[i]); }}void print(int i, int j){ if(!i) return ; if(dp[i][j] == dp[i-1][j]) print(i-1, j); else { print(i-1, j-v[i]); printf("%d ", v[i]); }} int main(){ int i; while(~scanf("%d%d", &vv, &n)) { for(i = 1; i <= n; i++) scanf("%d", v+i); memset(dp, 0, sizeof(dp)); for(i = 1; i <= n; i++) zero_dp(i); print(n, vv); printf("sum:%d\n", dp[n][vv]); } return 0;}
转载于:https://www.cnblogs.com/andre0506/archive/2012/09/19/2693440.html