记录路径的 01 背包．

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int score[N], cost[N];
int dp[1005];
int vis[N][1005];
int main()
{
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        int b, n;
        scanf("%d %d", &b, &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", score + i, cost + i);
        }
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++) {
            for (int j = b; j >= cost[i]; j--) {
                if (dp[j] < dp[j - cost[i]] + score[i]) {
                    dp[j] = dp[j - cost[i]] + score[i];
                    vis[i][j] = 1;
                }
            }
        }
        int sum = 0;
        stack<int> s;
        for (int i = n, j = b; i >= 1 && j >= 0; i--) {
            if (vis[i][j]) {
                sum += cost[i];
                s.push(i);
                j -= cost[i];
            }
        }
        printf("Case #%d:\n", cas++);
        printf("%d %d\n", dp[b], sum);
        while (!s.empty()) {
            printf("%d", s.top());
            s.pop();
            if (s.empty()) {
                printf("\n");
            } else {
                printf(" ");
            }
        }
    }
    return 0;
}