最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

有 $N$ 件 物品 和一个 容量 为 $V$ 的 背包

第 $i$ 件物品的 体积 是$v_i$, 价值 是$w_i$,每件 物品 只能使用一次

求解一种 方案，使得选择的 物品 的 总体积 不超过背包的 最大容量，且 总价值 最大

输出 字典序最小的方案

分析

本题是 背包DP 的经典变种模型 背包DP输出方案

输出方案 其实就是输出方案的 转移路径

我们先做一遍正常的 背包DP ，然后从 目标状态 倒推回 初始状态 的整个 转移路径 即可

说的白话一点就是，在考虑第 i 件物品时，选择了 选 还是 不选 的策略到达了第 i+1 件物品

伪代码如下：（参考oi wiki）

int v = V;  // 记录当前的存储空间

// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件)
{
  if (g[i][v])
  {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

当然也可以从 拓扑图 的角度来 分析理解，这次不额外展开，具体可以参考下面这篇博客，里面也有 DFS 的写法

AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】

这里主要展示 迭代 的写法（其实就是在跟踪状态转移的路径）

题目里还要求了 输出 字典序最小的方案

而在倒推 状态转移路径 的时候，只能在 分叉转移 的时候，即 当前 物品既可以 选 又可以 不选 时，优先 选

因此，我们本题的 背包DP 需要倒过来（从N递推到1）做，然后再 从1倒推回N 找出路径

这样在抉择时，如果出现 分叉转移，我们就优先 选 当前物品即可

01背包模型 $\mathrm{f[i][j]}$

状态表示$f(i,j)$—集合： 考虑后 i 个物品，且当前已使用体积不超过 j 的方案

状态表示$f(i,j)$—属性： 该方案的价值为最大值 $\max$

状态转移$f(i,j)$： $f(i,j) = \begin{cases} 不选第i个物品： &\max\{f(i+1,j)\} \\\ 选第i个物品：&\max\{f(i+1,j - v_i) + w_i\} \end{cases}$

Code

时间复杂度：$O(N \times V)$

路径追踪的 递归 写法可以参考这篇博客
AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];
int path[N], cnt;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; -- i)
    {
        for (int j = 0; j <= m; ++ j)
        {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    for (int i = 1, j = m; i <= n; ++ i)
    {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            path[cnt ++ ] = i;
            j -= v[i];
        }
    }
    for (int i = 0; i < cnt; ++ i) cout << path[i] << " ";
    cout << endl;
    return 0;
}