原题大意

01背包，但是要输出路径，按照序号和最小，字典序最小输出。

程序代码

可以用vis[i][j]，来记录路径。

#include <cstdio>
#include <cstring>
#include <iostream>

#define clr(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int MAXN = 111;
const int MAXB = 1111;

struct meal
{
    int score, cost;
} m[MAXN];

int B, N;
int dp[MAXB];
bool tmp[MAXN];
bool vis[MAXN][MAXB];

int main()
{
    int T, ce = 1;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &B, &N);
        for (int i = 1; i <= N; i++)
        {
            scanf("%d%d", &m[i].score, &m[i].cost);
        }

        clr(dp, 0);
        clr(tmp, 0);
        clr(vis, false);

        for (int i = 1; i <= N; i++)
        {
            for (int j = B; j >= 0; j--)
            {
                if (j >= m[i].cost)
                {
                    if (dp[j] < dp[j - m[i].cost] + m[i].score)
                    {
                        vis[i][j] = true;
                        dp[j] = dp[j - m[i].cost] + m[i].score;
                    }
                    else
                    {
                        vis[i][j] = false;
                    }
                }
            }
        }

        int t = B, cnt = 0;
        for (int i = N; i >= 1; i--)
        {
            if (vis[i][t])
            {
                tmp[i] = true;
                t -= m[i].cost;
                cnt++;
            }
        }

        printf("Case #%d:\n%d %d\n", ce++, dp[B], B - t);
        for (int i = 1; i <= N; i++)
        {
            if (tmp[i])
            {
                printf("%d%c", i, (--cnt == 0) ? '\n' : ' ');
            }
        }
    }

    return 0;
}

也可以用pre来记录选取的点

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
typedef long long ll;
int b, n, T, kase;
int s[maxn], c[maxn];
struct bag{
    int val;
    int sum;
    int pre;
}dp[maxn][maxn];
int main(){
    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        cin >> b >> n;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++){
            cin >> s[i] >> c[i];
        }
        for(int i = 1; i <= n; i++){
            for(int v = 0; v <= b; v++)
                dp[i][v] = dp[i-1][v];
            for(int v = b; v >= c[i]; v--){
                if(dp[i-1][v - c[i]].val + s[i] > dp[i][v].val){
                    dp[i][v].val = dp[i-1][v - c[i]].val + s[i];
                    dp[i][v].sum = dp[i-1][v - c[i]].sum + i;
                    dp[i][v].pre = i;
                }
                else if(dp[i-1][v - c[i]].val + s[i] == dp[i][v].val){
                    if(dp[i-1][v - c[i]].sum + i < dp[i][v].sum){
                        dp[i][v].sum = dp[i-1][v - c[i]].sum + i;
                        dp[i][v].pre = i;                        
                    }
                }
            }
        }
        int p[maxn], l = 0;
        int now = n, sum = b;
        int ans = 0;
        while(dp[now][sum].pre != 0){
            int cur = dp[now][sum].pre;
            sum -= c[cur];
            now = cur - 1;
            p[++l] = cur;
            ans+=c[cur];
        }
        printf("Case #%d:\n%d %d\n", ++kase, dp[n][b].val, ans);
        for(int i = l; i > 1; i--) printf("%d ", p[i]);
        if(l>=1)printf("%d\n", p[1]);
    }
    return 0;
}