用DP求出 01背包的最大价值后该如何求得这条路径，就是有多少种选取情况下可以达到这个最大价值呢？
在本次百度之星的比赛中，有毒的1004让我好好思考了这个问题：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int dp[105][1005]; int score[105], cost[105]; bool re[105][105]; int main() { int CASE; scanf("%d", &CASE); for(int cas = 1; cas <= CASE; ++cas) { int pre, n; scanf("%d%d", &pre, &n); for(int i = 1; i <= n; ++i) scanf("%d%d", &score[i], &cost[i]); memset(dp, 0, sizeof(dp)); memset(re, 0, sizeof(re)); for(int i = 1; i <= n; ++i) { for(int j = pre; j >= cost[i]; --j) { if(dp[i - 1][j] <= dp[i - 1][j - cost[i]] + score[i]) { re[i][j] = 1; dp[i][j] = dp[i - 1][j - cost[i]] + score[i]; } else dp[i][j] = dp[i - 1][j]; } for(int j = cost[i] - 1; j >= 0; --j) dp[i][j] = dp[i - 1][j]; } int ans = dp[n][pre]; int sum = 10005; int sum_cnt = 0; int con[105]; for(int i = n; i >= 1; --i) for(int j = pre; j >= 0; --j) { if(dp[i][j] == ans && re[i][j]) { int tsum = 0; int cnt = 0; int tmp[105]; int x, y; for(x = i, y = j; x >= 1 && y > 0; x -= 1) { if(re[x][y]) { y -= cost[x]; tsum += x; tmp[cnt++] = x; } } if(y > 0) continue; //for(int t = cnt - 1; t >= 0; --t) //printf("%d%c", tmp[t], t == 0 ? '\n' : ' '); if(tsum < sum) { sum = tsum; sum_cnt = cnt; for(int t = 0; t < cnt; ++t) con[t] = tmp[t]; } else if(tsum == sum) { int ok = 0; for(int k = cnt - 1, t = sum_cnt - 1; k >= 0 && t >= 0; --t, --k) { if(con[t] != tmp[k]) { ok = con[t] < tmp[k] ? 0 : 1; break; } } if(ok == 1) { sum_cnt = cnt; for(int t = 0; t < cnt; ++t) con[t] = tmp[t]; } } } } sum = 0; for(int i = 0; i < sum_cnt; ++i) sum += cost[con[i]]; printf("Case #%d:\n", cas); printf("%d %d\n", ans, sum); for(int i = sum_cnt - 1; i >= 0; --i) printf("%d%c", con[i], i == 0 ? '\n' : ' '); } return 0; }
2017百度之星1004 度度熊的午饭时光
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int dp[105][1005]; int score[105], cost[105]; bool re[105][1005];//一切问题的根源在于你的数组开小了 int main() { int CASE; scanf("%d", &CASE); for(int cas = 1; cas <= CASE; ++cas) { int pre, n; scanf("%d%d", &pre, &n); for(int i = 1; i <= n; ++i) scanf("%d%d", &score[i], &cost[i]); memset(dp, 0, sizeof(dp)); memset(re, 0, sizeof(re)); for(int i = 1; i <= n; ++i) { for(int j = pre; j >= cost[i]; --j) { if(dp[i - 1][j] <= dp[i - 1][j - cost[i]] + score[i]) { re[i][j] = 1; dp[i][j] = dp[i - 1][j - cost[i]] + score[i]; } else dp[i][j] = dp[i - 1][j]; } for(int j = cost[i] - 1; j >= 0; --j) dp[i][j] = dp[i - 1][j]; } int ans = dp[n][pre]; if(ans == 0) { printf("Case #%d:\n", cas); printf("0 0\n"); continue; } int sum = 10005; int sum_cnt = 0; int con[105]; for(int i = n; i >= 1; --i) for(int j = pre; j >= 0; --j) { if(dp[i][j] == ans && re[i][j]) { int tsum = 0; int cnt = 0; int tmp[105]; int x, y; for(x = i, y = j; x >= 1 && y > 0; x -= 1) { if(re[x][y]) { y -= cost[x]; tsum += x; tmp[cnt++] = x; } } if(y > 0) continue; //for(int t = cnt - 1; t >= 0; --t) //printf("%d%c", tmp[t], t == 0 ? '\n' : ' '); if(tsum < sum) { sum = tsum; sum_cnt = cnt; for(int t = 0; t < cnt; ++t) con[t] = tmp[t]; } else if(tsum == sum) { int ok = 0; for(int k = cnt - 1, t = sum_cnt - 1; k >= 0 && t >= 0; --t, --k) { if(con[t] != tmp[k]) { ok = con[t] < tmp[k] ? 0 : 1; break; } } if(ok == 1) { sum_cnt = cnt; for(int t = 0; t < cnt; ++t) con[t] = tmp[t]; } } } } sum = 0; for(int i = 0; i < sum_cnt; ++i) sum += cost[con[i]]; for(int i = 1; i <= n; ++i) { if(score[i] != 0 && cost[i] == 0) { con[sum_cnt++] = i; } } sort(con, con + sum_cnt); printf("Case #%d:\n", cas); printf("%d %d\n", ans, sum); for(int i = 0; i < sum_cnt; ++i) printf("%d%c", con[i], i == sum_cnt - 1 ? '\n' : ' '); } return 0; }
经过十几发的WA终于AC了这道有毒的题目，最后才发现原来一开始re数组开的是105*105，所以一直没有发现，天哪噜！！！
