[HDOJ6083] 度度熊的午饭时光（背包，记录路径）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6083

01背包加记录路径，用path(i,j)给转移时的状态打标记，倒推回去就行。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef pair<int, int> pii;
 5 const int maxn = 110;
 6 const int maxm = 1010;
 7 int m, n;
 8 int v[maxn], w[maxn];
 9 int f[maxm];
10 int path[maxn][maxm];
11 vector<int> tmp;
12 
13 signed main() {
14     // freopen("in", "r", stdin);
15     int T, _ = 1;
16     scanf("%d", &T);
17     while(T--) {
18         memset(path, 0, sizeof(path));
19         memset(f, 0, sizeof(f));
20         tmp.clear();
21         scanf("%d%d",&m,&n);
22         for(int i = 1; i <= n; i++) {
23             scanf("%d%d",&v[i], &w[i]);
24         }
25         for(int i = 1; i <= n; i++) {
26             for(int j = m; j >= w[i]; j--) {
27                 if(f[j] < f[j-w[i]]+v[i]) {
28                     f[j] = f[j-w[i]] + v[i];
29                     path[i][j] = 1;
30                 }
31             }
32         }
33         printf("Case #%d:
", _++);
34         int tot1 = 0, tot2 = 0;
35         for(int i = n, j = m; i >= 1; i--) {
36             if(path[i][j]) {
37                 tot1 += v[i]; tot2 += w[i];
38                 tmp.push_back(i);
39                 j -= w[i];
40             }
41         }
42         printf("%d %d
", tot1, tot2);
43         sort(tmp.begin(), tmp.end());
44         for(int i = 0; i < tmp.size(); i++) {
45             printf("%d%c", tmp[i], i==tmp.size()-1?'
':' ');
46         }
47     }
48     return 0;
49 }

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int maxn = 110;
const int maxm = 1010;
int m, n;
int v[maxn], w[maxn];
int f[maxm];
int path[maxn][maxm];
vector<int> tmp;

signed main() {
    // freopen("in", "r", stdin);
    int T, _ = 1;
    scanf("%d", &T);
    while(T--) {
        memset(path, 0, sizeof(path));
        memset(f, 0, sizeof(f));
        tmp.clear();
        scanf("%d%d",&m,&n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%d",&v[i], &w[i]);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= w[i]; j--) {
                if(f[j] < f[j-w[i]]+v[i]) {
                    f[j] = f[j-w[i]] + v[i];
                    path[i][j] = 1;
                }
            }
        }
        printf("Case #%d:
", _++);
        int tot1 = 0, tot2 = 0;
        for(int i = n, j = m; i >= 1; i--) {
            if(path[i][j]) {
                tot1 += v[i]; tot2 += w[i];
                tmp.push_back(i);
                j -= w[i];
            }
        }
        printf("%d %d
", tot1, tot2);
        sort(tmp.begin(), tmp.end());
        for(int i = 0; i < tmp.size(); i++) {
            printf("%d%c", tmp[i], i==tmp.size()-1?'
':' ');
        }
    }
    return 0;
}