【算法】背包类型动态规划

· · 算法·理论

约定

物品的总数为 n，背包的容量为 W，第 i 种物品的价值为 \text{price}_i、占用的背包容量为 \text{weight}_i、可选择的次数为 \text{number}_i，递推数组为 \text{dp}，采用滚动数组优化后的递推数组为 \text{dp}_r，但在代码中仍记作dp。除额外说明的情况，这些均是正整数。

如果一种类型的问题允许采用不同的问题作为基础（如多维费用背包既可以是多维费用的 0-1 背包，也可以是多维费用的完全背包），以 0-1 背包为基础。

本文中的数组大小仅是示例，与实际问题所需可能有出入。

其余均会在相应位置给出说明。

0-1 背包

0-1 背包是背包类型动态规划中最基础的问题。在 0-1 背包中，物品互不干扰，且每个物品仅可选择一次，要求所能取到的最大物品价值和。由于每个物品均仅有选与不选两种状态，这种背包被称为 0-1 背包。

骗分过样例，暴力出奇迹。

这个问题是很容易用 DFS 暴力解决的，它的时间复杂度为 \mathcal{O}(2^n)，不过这样非常低效。考虑贪心，但很容易构造数据使得贪心策略失效。

事实上，大部分背包问题的常见解法是动态规划。一般地，我们定义 \text{dp}_{i,j} 表示从前 i 个物品中选取若干个物品放入背包剩余容量为 j 的背包中，所能取得的最大价值和。

我们将遍历每个物品与每种背包容量。对于当前的物品，有两种情况：

  1. 如果当前的背包剩余容量不足以选择它，那么只能不选，即在背包剩余容量相同的情况下继承上一个物品的状态；
  2. 如果足够选择，那么若将它塞进背包中，就相当于在考虑前一个物品时减少了一定的背包剩余容量，同时得到了当前物品的价值。否则和情况 1 相同。

于是很容易得到状态转移方程为

\begin{cases} \max(\text{dp}_{i-1,j-\text{weight}_i}+\text{price}_i,\text{dp}_{i-1,j}),&j\ge\text{weight}_i\\ \text{dp}_{i-1,j},&\text{otherwise.} \end{cases}

其初始值为 \text{dp}_{i,0}=\text{dp}_{0,j}=0，最终答案为 \text{dp}_{n,W}。

int n,W,price[105],weight[105],dp[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j>=weight[i]) dp[i][j]=max(dp[i-1][j-weight[i]]+price[i],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][W];
    return 0;
}

接下来我们可以使用一种叫做“滚动数组”的优化方法。 ::::info[知识点-滚动数组]{open} 滚动数组是动态规划中一种极其重要的优化技巧，可以对空间复杂度进行革命性的优化。

举个例子，假设某状态 \text{dp}_{i,j} 的转移方程为

\text{dp}_{i,j}=\max(\text{dp}_{i-1,j},\text{dp}_{i-1,j-1})

通常我们要开一个二维数组进行递推。但是我们可以发现，在转移过程中，对于当前的 \text{dp}_{i,j}，它始终仅依赖 \text{dp}_{i-1,x} 进行转移，存储 \text{dp}_{i-2,x} 等以前的数据是不必要的。所以，我们可以用两个一维数组 \text{last},\text{now} 分别存储 \text{dp}_{i-1,x} 与 \text{dp}_{i,x}，每次从 \text{last} 进行转移，转移完成后，将 \text{now} 覆盖到 \text{last} 上继续转移。不过通常我们不会真的使用两个一维数组，因为覆盖需要不小的时间开销。对于例子中的状态，它的核心实现大致如下：

int dp[2][105];
for(int i=1,cur=0;i<=n;i++,cur^=1)
    for(int j=1;j<=n;j++) dp[cur][j]=max(dp[cur^1][j],dp[cur^1][j-1]);

如果依赖的维度更多，也可以通过类似的方式优化，不过会更加复杂。但这并不是终点，如果情况允许，我们可以直接在原基础上转移，这样就只剩下一个一维数组。

int dp[105];
for(int i=1;i<=n;i++)
    for(int j=n;j>=1;j--) dp[j]=max(dp[j],dp[j-1]);

这种方法需要格外注意，如果 \text{dp}_{r_j} 依赖之前的数据（比如 \text{dp}_{r_{j-1}}）进行转移，若还正序枚举 j，就会出现 \text{dp}_{r_{j-1}} 已经转移，但 \text{dp}_{r_j} 仍依赖其进行转移的情况，进而导致答案出错。所以我们需要逆序枚举，这样 \text{dp}_{r_{j-1}} 才是上一轮的数据。类似的，如果依赖之后的数据，就需要正序枚举。当然这也不是绝对的，要是我们需要当前轮而非上一轮的数据进行转移，就恰恰相反，比如之后的完全背包。

有时，如果在优化前的某些情况会直接继承上一个维度同样位置的数据，这些情况在优化时可以直接忽略，因为此时的数组中存储的就是上一个维度的数据。

滚动数组有一个缺点，就是可能会丢失一些信息。例如，有些时候可能要输出方案，这时使用滚动数组会抛弃前面的数据，不方便记录。

滚动数组并不仅仅适用于二维动态规划，它同样可以用于更高维度。比如 CSP-J 2025 T4 的这篇题解（没交到题解区，悲）中，就对三维的递推数组进行了滚动数组优化。

总之，它的好处在于能够大大优化空间复杂度，但缺点在于不容易理解、可读性下降及部分信息的丢失。 :::: 在这里，\text{dp}_{i,j} 始终仅依赖 \text{dp}_{i-1,x} 进行转移，因此我们可以通过滚动数组将维度 i 优化掉。

int n,W,price[105],weight[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
        for(int j=W;j>=weight[i];j--) dp[j]=max(dp[j-weight[i]]+price[i],dp[j]);
    cout<<dp[W];
    return 0;
}

完全背包

完全背包相比 0-1 背包只有一个区别，就是每种物品都能选择无限个。这很容易解决，我们加一个循环尝试选取 k 个第 i 种物品，取最终结果的最大值就行。其状态转移方程为

\text{dp}_{i,j}=\max\limits_{0\le k,k\cdot\text{weight}_i\le j}(\text{dp}_{i-1,j-k\cdot\text{weight}_i}+k\cdot\text{price}_i)

这样效率是很低的，因为有一个三重循环。

我们可以注意到，最优的选择 k 个当前物品的方案可以从选择 k-1 个当前物品的方案转移过来，而选择 k-1 个物品的方案就是 \text{dp}_{i,j-\text{weight}_i}。再加上考虑不选的情况，我们可以得到完全背包的状态转移方程为

\begin{cases} \max(\text{dp}_{i,j-\text{weight}_i}+\text{price}_i,\text{dp}_{i-1,j}),&j\ge\text{weight}_i\\ \text{dp}_{i-1,j},&\text{otherwise.} \end{cases}

按照同样的方法，采用滚动数组就能继续优化。但这下出了问题，\text{dp}_{i,j-\text{weight}_i}（即 \text{dp}_{r_{j-\text{weight}_i}}）是本轮转移后的数据，我们没法用和 0-1 背包一样的写法。转念一想，如果我们正序枚举 j，那么对于当前的 j，\text{dp}_{r_x}(x<j) 就都转移过了，也就都存储着 \text{dp}_{i,x}。而此时 \text{dp}_{r_j} 还没有更新，也就是存储着 \text{dp}_{i-1,j}。刚刚好！这下问题就迎刃而解了。

int n,W,price[105],weight[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
        for(int j=weight[i];j<=W;j++) dp[j]=max(dp[j-weight[i]]+price[i],dp[j]);
    cout<<dp[W];
    return 0;
}

一定要记住，0-1 背包逆序枚举容量，完全背包正序枚举容量。

多重背包

在多重背包中，每种物品都有其可取用的次数限制。要解决这个问题，我们可以像完全背包一样，每种物品都尝试选取 k 个，取最大值。状态转移方程为

\text{dp}_{i,j}=\max\limits_{0\le k\le\text{number}_i,k\cdot\text{weight}_i\le j}(\text{dp}_{i-1,j-k\cdot\text{weight}_i}+k\cdot\text{price}_i) 
int n,W,price[105],weight[105],number[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i]>>number[i];
    for(int i=1;i<=n;i++)
        for(int j=W;j>=weight[i];j--)
            for(int k=0;k<=number[i]&&k*weight[i]<=j;k++) dp[j]=max(dp[j-k*weight[i]]+k*price[i],dp[j]);
    cout<<dp[W];
    return 0;
}

这样写可能有点丑。事实上，“第 i 种物品能取 \text{number}_i 次”和“有 \text{number}_i 个第 i 种物品”是等价的，所以我们其实只要在 0-1 背包的基础上再套一个循环，就能极其简单地解决问题。

int n,W,price[105],weight[105],number[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i]>>number[i];
    for(int i=1;i<=n;i++)
        for(int k=1;k<=number[i];k++)
            for(int j=W;j>=weight[i];j--) dp[j]=max(dp[j-weight[i]]+price[i],dp[j]);
    cout<<dp[W];
    return 0;
}

但接下来想要优化可就没那么简单了。

二进制优化

二进制优化可行的前提是

\forall n\in\mathbb{N}^+,\exists!(k,x)\in\mathbb{N}^+\times\mathbb{N},n=\sum_{i=0}^{k-1} 2^i+x\land 0\le x<2^k\tag{A} \forall m\in\mathbb{N}\cap[0,n],\exists S\subseteq\{2^0,2^1,\dots,2^{k-1},x\}\land\sum_{i\in S}i=m\tag{B}

我们来证明一下。 ::::info[证明] 该证明由 Gen AI 生成，模型版本为 Kimi K2 Thinking。

对于命题 (A)，有

\sum_{i=0}^{k-1} 2^i+x=(2^k-1)+x\Longrightarrow n=(2^k-1)+x \end{aligned}

令

k=\lfloor\log_2(n+1)\rfloor,x=n-(2^k-1)

则

k\le\log_2(n+1)<k+1&\Longrightarrow 2^k-1\le n<2^{k+1}-1\\ &\Longrightarrow 0\le n-(2^k-1)<2^k\\ &\Longrightarrow 0\le x<2^k \end{aligned} \\ \begin{aligned} n\in\mathbb{N}^+&\Longrightarrow n\ge 1\\ &\Longrightarrow \lfloor\log_2(n+1)\rfloor=k\ge 1\\ \end{aligned}

存在性得证。

假设 (k_1,x_1),(k_2,x_2) 均满足条件，且 k_1\le k_2，则

n=(2^{k_1}-1)+x_1=(2^{k_2}-1)+x_2,0\le x_i<2^{k_i}\Longrightarrow x_2-x_1=2^{k_2}-2^{k_1}

若 k_1<k_2，则

k_1+1\le k_2\Longrightarrow 2^{k_1+1}-1\le 2^{k_2}-1\tag{1}

由 n=(2^{k_1}-1)+x_1 有

n=(2^{k_1}-1)+x_1<(2^{k_1}-1)+2^{k_1}=2^{k_1+1}-1\tag{2}

由 n=(2^{k_2}-1)+x_2 有

n=(2^{k_2}-1)+x_2\ge 2^{k_2}-1\tag{3}

将 (1),(2),(3) 联立，有

n<2^{k_1+1}-1\le 2^{k_2}-1\le n

该式恒不成立，故原假设不成立，即 k_1\ge k_2。又 k_1\le k_2，故 k_1=k_2，进而 x_1=x_2。

因此表示存在且唯一，原命题得证。

对于命题 (B)，若 m<x，必有

0\le m\le 2^k-1

将 m 表示为二进制形式，易得满足要求的子集 S。

若 m\ge x，令 y=m-x，则

0\le y\le n-x=(2^k-1)+x-x=2^k-1

将 y 表示为二进制形式，易得满足要求的子集 S'。再令 S=S'\cup\{x\}，于是

\sum_{i\in S}i=x+\sum_{i\in S'}i=x+y=m

原命题得证。 :::: 说白了，就是

  1. 任何正整数 n 均可以唯一地表示为 2^k-1(2^0+2^1+\dots+2^{k-1}) 与非负整数 x(0\le x<2^k) 之和；
  2. 任何整数 m\in[0,n] 均可以表示为集合 \{2^0,2^1,\dots,2^{k-1},x\} 中的一个子集的元素之和。

这意味着，我们可以将“有 \text{number}_i 个第 i 种物品”拆成“有 2^0,2^1,\dots,2^{k-1},x 个第 i 种物品”，然后把每 2^0,2^1,\dots,2^{k-1},x 个物品看作一个物品进行转移，这样做需要进行转移的次数就少了许多。

int n,W,price[105],weight[105],number[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i]>>number[i];
    for(int i=1;i<=n;i++)
    {
        int k=1;
        while(k<=number[i])
        {
            for(int j=W;j>=k*weight[i];j--) dp[j]=max(dp[j],dp[j-k*weight[i]]+k*price[i]);
            number[i]-=k,k<<=1;
        }
        if(number[i])
            for(int j=W;j>=number[i]*weight[i];j--)
                dp[j]=max(dp[j],dp[j-number[i]*weight[i]]+number[i]*price[i]);
    }
    cout<<dp[W];
    return 0;
}

混合背包

混合背包问题意味着有些物品只能取一次，有些物品能取无数次，有些物品能取的次数有一定的限制……听起来就很难，不过实际上混合背包非常简单。我们保持状态定义不变，依旧遍历每个（种）物品，并按照当前物品的类型选用不同问题的代码就行。

OI-Wiki 上的伪代码可以很好地解释它的思路。

for(循环物品种类)
{
    if(是 0-1 背包) 套用 0-1 背包代码;
    else if(是完全背包) 套用完全背包代码;
    else if(是多重背包) 套用多重背包代码;
}

分组背包

在 0-1 背包中，物品互不干扰。但在分组背包中，物品被分为 c 组，每组中的物品都互斥，最多只能选择其中一个。为了方便，我们先改令 \text{weight}_{i,k} 表示第 i 组第 k 个物品占用的背包容量，\text{price}_{i,k} 表示该物品的价值，\text{number}_i 表示第 i 组的物品数量。接下来，我们遍历每一组内的物品，并进行抉择。考虑定义 \text{dp}_{i,j} 表示处理完前 i 组物品且背包剩余容量为 j 时，所能取得的最大价值和。状态转移方程为

\text{dp}_{i,j}=\max(\text{dp}_{i-1,j},\max\limits_{1\le k\le\text{number}_i,j\ge \text{weight}_{i,k}}(\text{dp}_{i-1,j-\text{weight}_{i,k}}+\text{price}_{i,k}))

这个转移方程如何保证每组中最多只选择一个物品的呢？很简单，因为 \text{dp}_{i,j} 仅依赖 \text{dp}_{i-1,x} 进行转移，也就是说，每个物品都是单独考虑，最终再取所有情况的最大值，两个物品的状态之间并没有联系，也就不可能选到两个或更多物品。

然后我们再进行滚动数组优化即可。

struct group
{
    int number,price[105],weight[105],mi;
}a[105];
int W,c,dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>c;
    for(int i=1;i<=c;i++)
    {
        cin>>a[i].number;
        for(int j=1;j<=a[i].number;j++) cin>>a[i].weight[j]>>a[i].price[j],a[i].mi=min(a[i].mi,a[i].weight);
    }
    for(int i=1;i<=c;i++)
        for(int j=W;j>=a[i].mi;j--)
            for(int k=1;k<=a[i].number;k++) dp[j]=max(dp[j],dp[j-a[i].weight[k]]+a[i].price[k]);
    cout<<dp[W];
    return 0;
}

多维费用背包

在多维费用背包中，选择一个物品需要消耗多种不同的资源。为了方便，我们设第 i 个物品对第 j 种资源的消耗为 \text{weight}_{i,j}，第 i 种资源的上限为 W_i，共有 m 种资源。很容易想到，我们可以用不同的维度记录不同类型的资源消耗，也就是把状态定义为 \text{dp}_{i,j_1,j_2,\dots,j_m}。状态转移方程为

\begin{cases} \max(\text{dp}_{i-1,j_1-\text{weight}_{i,1},j_2-\text{weight}_{i,2},\dots,j_m-\text{weight}_{i,m}}+\text{price}_i,\text{dp}_{i-1,j_1,j_2,\dots,j_m}),&j_x\ge\text{weight}_{i,x}\\ \text{dp}_{i-1,j_1,j_2,\dots,j_m},&\text{otherwise.} \end{cases}

不用说也知道这样做时空复杂度是惊人的！能优化吗？很可惜，一般情况下，每个资源维度都是必要不可缺少的，我们只能用滚动数组把 i 优化掉。不过在实际中，空间应该是会给够的。

这里只给出二维费用背包的代码，更高维度或通用的代码请自行研究。

int n,m,W[105],price[105],weight[105][105],dp[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>W[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>weight[i][j];
        cin>>price[i];
    }
    for(int i=1;i<=n;i++)
        for(int j1=W[1];j1>=weight[i][1];j1--)
            for(int j2=W[2];j2>=weight[i][2];j2--)
                dp[j1][j2]=max(dp[j1][j2],dp[j1-weight[i][1]][j2-weight[i][2]]+price[i]);
    cout<<dp[W[1]][W[2]];
    return 0;
}

可行性背包

可行性背包并不要求能取到的最大价值和，只是要判断是否能刚好取到某个价值 V。

显然，我们不得不把价值塞到状态的下标中，不然几乎没法转移。由于我们只关心能不能取到，我们可以定义 \text{dp}_{i,j,k}\in\{0,1\}，表示从前 i 个物品中选取，共占用了 j 的背包容量，且价值和为 k 的情况是否存在。状态值为 0 表示不存在，反之亦然。

在转移中，只要 \text{dp}_{i-1,j,k} 或者 \text{dp}_{i-1,j-\text{weight}_i,k-\text{price}_i} 中的任意一个值为 1，\text{dp}_{i,j,k} 必然也为 1。这是逻辑或的计算方式，所以我们利用逻辑或进行状态转移。即转移方程为

\text{dp}_{i,j,k}=\text{dp}_{i-1,j,k}\lor\text{dp}_{i-1,j-\text{weight}_i,k-\text{price}_i}

再加上滚动数组优化即可。

int n,W,V,price[105],weight[105];
bool dp[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n>>V;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    dp[0][0]=true;
    for(int i=1;i<=n;i++)
        for(int j=W;j>=weight[i];j--)
            for(int k=V;k>=price[i];k--) dp[j][k]=dp[j][k]||dp[j-weight[i]][k-price[i]];
    bool can=false;
    for(int j=0;j<=W;j++) can=can||dp[j][V];
    cout<<(can?"Yes":"No");
    return 0;
}

当然，在转移过程中检查能不能取到是完全可行的，并且这会节省大量的时间。

另一种办法，我们定义 \text{dp}_{i,k} 为从前 i 个物品中选取价值和为 k 的物品最少所需的背包容量，有

\text{dp}_{i,k}=\min(\text{dp}_{i,k},\text{dp}_{i-1,k-\text{price}_i}+\text{weight}_i)

最后只要判断能否用不超过 W 的质量取到价值和为 V 的物品即可。再利用滚动数组优化，即可得到一个时间复杂度 \mathcal{O}(nV)，空间复杂度 \mathcal{O}(V) 的做法。

int n,W,V,price[105],weight[105],dp[105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n>>V;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    fill(dp+1,dp+V+1,INT_MAX);
    for(int i=1;i<=n;i++)
        for(int k=V;k>=price[i];k--) dp[k]=min(dp[k],dp[k-price[i]]+weight[i]);
    cout<<(dp[V]<=W?"Yes":"No");
    return 0;
}

但这种做法也有缺点。首先，它无法输出具体方案。其次，如果问题还要求一个取到特定的需求容量或者要求方案数，这种方法也无法胜任。

其他问题

求方案总数

求方案总数问题通常是求有多少种方案使得最终取出的价值和为 V。

这很简单，我们定义 \text{dp}_{i,j,k} 表示从前 i 个物品中选取若干个物品放入背包剩余容量为 j 的背包中，价值和为 k 的方案总数，就能得到状态转移方程为

\text{dp}_{i,j,k}=\text{dp}_{i,j,k}+\text{dp}_{i,j-\text{weight}_i,k-\text{price}_i} 
int n,W,V,price[105],weight[105],dp[105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n>>V;
    dp[0][0]=1;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
        for(int j=W;j>=weight[i];j--)
            for(int k=V;k>=price[i];k--) dp[j][k]+=dp[j-weight[i]][k-price[i]];
    int ans=0;
    for(int i=0;i<=W;i++) ans+=dp[i][V];
    cout<<ans;
    return 0;
}

求最优方案

求最优方案问题要求在求最大价值和外，还需要输出具体选了哪些物品。

首先假设只有一个最优方案，并且升序输出物品编号。由于上面说到滚动数组会造成信息丢失，我们必须采用朴素的二维数组进行递推。递推完成后，我们可以从最后一个物品开始往前遍历，同时维护一个变量 W_\text{now} 记录遍历到当前（第 i 个）物品时的背包剩余容量。如果最优方案中选择了当前物品，则对应的状态必然是从 \text{dp}_{i-1,j-\text{weight}_i}+\text{price}_i 转移过来的。所以我们只要判断 \text{dp}_{i,W_\text{now}} 与它是否相等就能知道第 i 个物品有没有选。如果选择了，就将当前物品加入选择方案，并更新 W_\text{now}。

不过这样会有个问题，如果选与不选当前物品的价值和相同，按上面的思路，这会被默认为选择了当前物品。但是这相比不选的情况，背包剩余容量更少了，却没有得到更大的价值和。所以我们需要判断选择当前物品的价值是否严格大于不选择当前物品的价值，如果是才选择当前物品。

int n,W,price[105],weight[105],dp[105][105];
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j>=weight[i]) dp[i][j]=max(dp[i-1][j-weight[i]]+price[i],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    int W_now=W;
    for(int i=n;i>=1;i--)
    {
        if(W_now>=weight[i]&&dp[i][W_now]==dp[i-1][W_now-weight[i]]+price[i]&&dp[i][W_now]>dp[i-1][W_now])
        {
            ans.push_back(i);
            W_now-=weight[i];
        }
    }
    for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<' ';
    return 0;
}

那么如果有多个最优方案怎么办呢？也很简单，我们用 DFS 各尝试一遍选与不选就行。

int n,W,price[105],weight[105],dp[105][105];
vector<vector<int> > ans;
vector<int> temp;
void DFS(int i,int W_now)
{
    if(i==0)
    {
        ans.push_back(temp);
        return;
    }
    if(dp[i][W_now]==dp[i-1][W_now]) DFS(i-1,W_now);
    if(W_now>=weight[i]&&dp[i][W_now]==dp[i-1][W_now-weight[i]]+price[i])
    {
        temp.push_back(i);
        DFS(i-1,W_now-weight[i]);
        temp.pop_back();
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=W;j++)
        {
            if(j>=weight[i]) dp[i][j]=max(dp[i-1][j-weight[i]]+price[i],dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    DFS(n,W);
    for(int i=0;i<ans.size();i++)
    {
        for(int j=ans[i].size()-1;j>=0;j--) cout<<ans[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

求最优方案总数

求最优方案总数，我们可以同时维护方案数与最大价值和两个数组，在转移中统计当前最优方案总数，如果最大价值和更新就重新统计。

这个应该很简单，代码就不给出了。

求第 k 优解

求第 k 优解问题需要求出在所有组合方案中第 k 大的价值和（这里将价值和相同的方案视为一个）。

由于一般的背包问题定义的都是最大的价值和，我们不能再沿用这个状态定义。不妨定义 \text{dp}_{i,j,t} 表示从前 i 个物品中选取若干个物品放入背包剩余容量为 j 的背包中，所能取得的第 t 优解。

\text{dp}_{i,j,t}=f_t(\{\text{dp}_{i-1,j,1},\dots,\text{dp}_{i-1,j,k}\}\cup\{\text{dp}_{i-1,j-\text{weight}_i,1}+\text{price}_i,\dots,\text{dp}_{i-1,j-\text{weight}_i,k}+\text{price}_i\})

其中 f_t(S) 表示集合 S 中第 t 大的元素。

考虑代码实现。我们首先实现 f_t()，这本质上就是将两个序列合并、排序并去重。我们可以使用双指针高效地同时完成这三个步骤。可以发现，合并完成后的序列实际上就是 \text{dp}_{i,j,x}，所以我们直接把合并后的序列覆盖到 \text{dp}_{i,j,x} 就行。

有些时候，合并后的序列长度不足 t。这时我们用INT_MIN标记它为不可达即可。

int n,W,k,price[105],weight[105],dp[105][105];
void merge(int a[],int b[])
{
    int i=1,j=1,cnt=1,temp[105];
    while(i<=k&&j<=k&&cnt<=k)
    {
        if(a[i]==INT_MIN&&b[j]==INT_MIN) break;
        if(a[i]>b[j]) temp[cnt++]=a[i++];
        else if(a[i]<b[j]) temp[cnt++]=b[j++];
        else temp[cnt++]=a[i++],j++;
    }
    while(i<=k&&cnt<=k&&a[i]!=INT_MIN) temp[cnt++]=a[i++];
    while(j<=k&&cnt<=k&&b[j]!=INT_MIN) temp[cnt++]=b[j++];
    cnt--;
    for(int i=1;i<=cnt;i++) a[i]=temp[i];
    for(int i=cnt+1;i<=k;i++) a[i]=INT_MIN;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>k>>W>>n;
    for(int i=1;i<=n;i++) cin>>weight[i]>>price[i];
    for(int i=0;i<=W;i++)
        for(int j=1;j<=k;j++) dp[i][j]=INT_MIN;
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=W;j>=weight[i];j--)
        {
            int b[105];
            for(int t=1;t<=k;t++)
            {
                if(dp[j-weight[i]][t]==INT_MIN) b[t]=INT_MIN;
                else b[t]=dp[j-weight[i]][t]+price[i];
            }
            merge(dp[j],b);
        } 
    }
    cout<<(dp[W][k]!=INT_MIN?dp[W][k]:-1);
    return 0;
}

更新记录