背包问题 | 动态规划

参考《算法竞赛进阶指南》、AcWing题库

背包问题

0/1背包

模型介绍

给定 $N$ 个物品，其中第 $i$ 个物品的体积为 $V_{i}$，价值为 $W_{i}$ 。有一容积为 $M$ 的背 包，要求选择一些物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的价位总 和最大。

根据上一节线性 DP 的知识，读者应该很容易想到依次考虑每个物品是否放入背 包，用 “已经处理的物品数” 作为 DP 的 “阶段”，以 “背包中已经放入的物品总体积”作为附加维度。

$F[i, j]$ 表示从前 $i$ 个物品中选出了总体积为 $j$ 的物品放入背包，物品的最大价值 和。

$$F[i, j]=\max \begin{cases}F[i-1, j] & \text { 不选第 } i \text { 个物品 } \\ F\left[i-1, j-V_{i}\right]+W_{i} & \text { if } j \geq V_{i} \quad \text { 选第 } i \text { 个物品 }\end{cases}$$

初值: $F[0,0]=0$，其余均为负无穷，目标: $\max _{0 \leq j \leq M}\{F[N][j]\}$ 。

memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++)
        f[i][j] = f[i - 1][j];
    for (int j = v[i]; j <= m; j++)
        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}

通过 DP 的状态转移方程，我们发现，每一阶段 $i$ 的状态只与上一阶段 $i-1$ 的 状态有关。在这种情况下，可以使用称为 “滚动数组” 的优化方法，降低空间开销。

int f[2][MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++)
        f[i & 1][j] = f[(i - 1) & 1][j];
    for (int j = v[i]; j <= m; j++)
        f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; j++)
    ans = max(ans, f[n & 1][j]);

通过 DP 的状态转移方程，我们发现，每一阶段 $i$ 的状态只与上一阶段 $i-1$ 的 状态有关。在这种情况下，可以使用称为 “滚动数组” 的优化方法，降低空间开销。

在上面的程序中，我们把阶段 $i$ 的状态存储在第一维下标为 $i \& 1$ 的二维数组中。 当 $i$ 为奇数时，$i \& 1$ 等于 1 ; 当 $i$ 为偶数时，$i \& 1$ 等于 0 。因此，DP 的状态就相当于 在 $F[0][\;]$ 和 $F[1][\;]$ 两个数组中交替转移，空间复杂度从 $O(N M)$ 降低为 $O(M)$ 。

进一步分析上面的代码，容易发现，在每个阶段开始时，实际上执行了一次从$F[i-1][\;]$ 到 $F[i][\;]$ 的拷贝操作。这提示我们可以进一步省略掉 $F$ 数组的第一维，只用一维数组，即当外层循环到第 $i$ 个物品时，$F[j]$ 表示背包中放入总体积为 $j$ 的物品的最大价值和。

int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--)
        //没更新前f[j]已经有值，是f[i - 1][j]
        f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++)
    ans = max(ans, f[j]);

请注意上面的代码片段中特别标注的部分一一我们使用了倒序循环。循环到 $j$ 时:

1. $F$ 数组的后半部分 $F[j \sim M]$ 处于 “第 $i$ 个阶段” ，也就是已经考虑过放入第 $i$ 个物品的情况。

2. 前半部分 $F[0 \sim j-1]$ 处于 “第 $i-1$ 个阶段”，也就是还没有第 $i$ 个物品更新。

接下来 $j$ 不断减小，意味着我们总是用 “第 $i-1$ 个阶段” 的状态向 “第 $i$ 个阶段” 的状态进行转移，符合线性 DP 的原则，进而保证了第 $i$ 个物品只会被放入背包一次。如下图所示。

然而，如果使用正序循环，假设 $F[j]$ 被 $F\left[j-V_{i}\right]+W_{i}$ 更新，接下来 $j$ 增大到 $j+V_{i}$ 时，$F\left[j+V_{i}\right]$ 又可能被 $F[j]+W_{i}$ 更新。此时，两个都处于 “第 $i$ 个阶段” 的 状态之间发生了转移，违背了线性 DP 的原则，相当于第 $i$ 个物品被使用了两次。如 下图所示。

所以，在上面的代码中必须用倒序循环，才符合 $0 / 1$ 背包问题中每个物品是唯一的、只能放入背包一次的要求。

---

初始化细节

体积最多是V：

• 初始化：f[0 ~ V] = 0
• 状态计算：利用f[j]进行转移，必须要有j >= 0

体积恰好是V：

• 初始化：f[0] = 0, f[1 ~ V] = 无效状态
• 状态计算：利用f[j]进行转移，必须要有j >= 0

体积至少是V：

• 初始化：f[0] = 0, f[1 ~ V] = 无效状态
• 状态计算：利用f[j]进行转移，j可以是负数

无效状态：使得在状态计算时不使用无效状态进行更新

• 求最大价值：$-\infty$
• 求最小价值: $+\infty$
• 求方案数：无效状态：0，有效状态：1（如f[0] = 1表示什么都不选且体积为0，这有1种方案）

要求恰好装满背包,那么在初始化时除了 $F[0]$ 为 0，其它 $F[1\cdots V]$ 均设为 $-\infty$，这样就可以保证最终得到的 $F[V]$ 是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满, 而是只希望价格尽量大, 初始化时应该将 $F[0]\;,\;F[1\cdots V]$ 全部设为 0 。

初始化的 $F$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。

• 就是看什么都不装时的初始值

• 如果要求背包恰好装满, 那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被设置为无效状态，如求最大价值时设置为 $-\infty$
• 如果背包并非必须被装满，那么任何容量的背包，都有一个合法解“什么都不装”，这个解的价值为 0 ，所以初始时状态的值也就全部为 0 了。

---

423. 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

为此，他想拜附近最有威望的医师为师。

医师为了判断他的资质，给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入文件的第一行有两个整数 $T$ 和 $M$，用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

数据范围

$1 \le T \le 1000$,
$1 \le M \le 100$

输入样例：

70 3
71 100
69 1
1 2 

输出样例：

3 

算法分析

我们把 $m$ 个单位时间看做是 背包的容量

每株草药看做是 物品 ，草药采集所需时间看做是 物品的体积，草药的价值看做是 物品的价值

那么本题就可以看做是一个 背包问题 了

由于每株草药只有一个，也就是要么采，要么不采两种方案，所以该题是一个 01背包 模型

Solution

#include <iostream>
using namespace std;
const int N = 1010;
int f[N], t[N], w[N];
int main() {
    int T, m;
    cin >> T >> m;
    for (int i = 1; i <= m; ++i) cin >> t[i] >> w[i];
    for (int i = 1; i <= m; ++i) {
        //未更新前f[j] = f[i - 1][j]
        //对于j < t[i]，f[j]不会更新，保持f[i - 1][j],也就是不选第i个
        for (int j = T; j >= t[i]; --j) {
            
            f[j] = max(f[j], f[j - t[i]] + w[i]);
        }
    }
    cout << f[T];
}

---

1024. 装箱问题

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

$0 < V \le 20000$,
$0 < n \le 30$

输入样例：

24
6
8
3
12
7
9
7 

输出样例：

0 

算法分析

本题也是一个 01背包 的题目

可以很直接的通过题目的字眼分析出来 01背包模型

一共有 $n$ 个物品，$m$ 的容量，每个物品有一个体积 $v_i$

而题目没有直接给出物品的 价值，但是题目要求我们选择物品的时候，在体积不超过容量的情况下最大

因此我们可以抽象出来物品的 价值$w_i$ 就是物品的 体积$v_i$

然后就是经典的 01背包的DP模型

Solution

#include <iostream>
using namespace std;
const int N = 20010;
int v[N], f[N];
int main() {
    int V, n;
    cin >> V >> n;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + v[i]);
        }
    }
    cout << V - f[V];
}

---

426. 开心的金明

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。

于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。

他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v[j]$，重要度为 $w[j]$，共选中了 $k$ 件物品，编号依次为 $j_1，j_2，…，j_k$，则所求的总和为：

$$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+…+v[j_k] \times w[j_k]$$

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件的第 $1$ 行，为两个正整数 $N$ 和 $m$，用一个空格隔开。（其中 $N$ 表示总钱数，$m$ 为希望购买物品的个数）

从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数 $v$ 和 $p$。（其中 $v$ 表示该物品的价格，$p$ 表示该物品的重要度）

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 $10^8$）。

数据范围

$1 \le N < 30000$,
$1 \le m < 25$,
$0 \le v \le 10000$,
$1 \le p \le 5$

输入样例：

1000 5
800 2
400 5
300 5
400 3
200 2 

输出样例：

3900 

算法分析

(DP,背包问题) $O(nm)$

将原问题做如下转化

• 总钱数相当于背包总容量；
• 每件物品的价格相当于体积；
• 每件物品的价格乘以重要度相当于价值；

那么就变成了经典的01背包问题。

Solution

#include <iostream>
using namespace std;
const int N = 30010;
int v[N], p[N];
int f[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> v[i] >> p[i];
    for (int i = 1; i <= m; ++i) {
        for (int j = n; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]] + v[i] * p[i]);
        }
    }
    cout << f[n];
}

---

8. 二维费用的背包问题

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式

第一行三个整数，$N,V, M$，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 $N$ 行，每行三个整数 $v_i, m_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$
$0 \lt V, M \le 100$
$0 \lt v_i, m_i \le 100$
$0 \lt w_i \le 1000$

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6 

输出样例：

8 

算法分析

这道题目跟 0/1 背包很像，只不过实在 0/1 背包的基础上加上了一个重量限制。

01 背包的动态转移方程是

$f[i,j]\ =\ max\ (f[i - 1][j],\;f[i - 1][j - v_i] + w_i)$

那么这个多了个重量，那么可以再开一维，变成三维

$f[i][j][k] \ = \ max \ (f[i - 1][j][k],\;f[i - 1][j - v_i][k - m_i] + w_i)$

同 01 背包，它也可以压缩亿下空间，于是变成了

$f[j][k] =\ max\ (f[j][k],\;f[j - v_i][k-m_i] + w_i)$

动态转移方程出来了，那么写代码也就轻松了。

Solution

#include <iostream>
using namespace std;
const int N = 1005;
int f[105][105];
int v[N], m[N], w[N];
int main() {
    int n, V, M;
    cin >> n >> V >> M;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> m[i] >> w[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            for (int k = M; k >= m[i]; --k) {
                f[j][k] = max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
            }
        }
    }
    cout << f[V][M];
}

---

1022. 宠物小精灵之收服（二维费用）

题目描述

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围

$0 < N \le 1000$,
$0 < M \le 500$,
$0 < K \le 100$

输入样例1：

10 100 5
7 10
2 40
2 50
1 20
4 20 

输出样例1：

3 30 

输入样例2：

10 100 5
8 110
12 10
20 10
5 200
1 110 

输出样例2：

0 100 

算法分析

• 最多收服多少个小精灵

二维费用0/1背包问题

• 花费1：小智的精灵球数量

• 花费2：皮卡丘初始的体力值

状态表示：

• i：只考虑前i个物品（只在前i个小精灵中进行捕捉 ）
• j：花费1（所用的精灵球数量）不超过j
• k：花费2（总共消耗的体力值）不超过k
• f[i][j][z]：只在前 i 个小精灵中捕捉，且所用球数不超过 j ，消耗体力值不超过 k 的情况下，能捕捉小精灵数量的最大值
• need[i]:收服第 i 个小精灵需要的精灵球的数量
• harm[i]:收服第 i 个小精灵过程中对皮卡丘造成的伤害，即消耗的体力值

状态计算：

• 不选第 i 个：f[i-1][j][k]
• 选第 i 个：f[i-1][j - need[i]][k - harm[i]] + 1
• f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - need[i]][k - harm[i]] + 1)

注意：因为题目中说明当所消耗的体力等于皮卡丘的体力时，也是不能捕捉成功的，所以 k 的最大值即为皮卡丘的体力-1，因此皮卡丘的体力值需在Vh - 1时开始

最多收服的小精灵的数量为f[n,Vn,Vh - 1]

在收服最多数量时，且使消耗的最少体力，从Vh - 1开始枚举到0，找出收服数量为f[n,Vn,Vh - 1]的最小k值

• 皮卡丘最大剩余体力

f[n,Vn,Vh - 1]：在所有小精灵中使用全部的精灵球且皮卡丘不挂的前提下所能捕捉小精灵的最大数量

要使皮卡丘剩余体力最大，我们可以倒序遍历第三维 k，即从可消耗最大体力来开始倒序遍历，那么当使用 k (k < Vh - 1) 体力时仍能捕捉最多小精灵的话，皮卡丘可以省点体力

那么当全部遍历完成后，我们就可以得到皮卡丘可以节省的最大总体力数，再用皮卡丘的体力 - 捕获相同数量最小可消耗体力 = 最大剩余体力数

Solution

#include <iostream>
using namespace std;
const int N = 1010;
int need[N], harm[N];
int f[N][N];
int main() {
    int Vn, Vh, n;
    cin >> Vn >> Vh >> n;
    for (int i = 1; i <= n; ++i) cin >> need[i] >> harm[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = Vn; j >= need[i]; --j) {
            for (int k = Vh - 1; k >= harm[i]; --k) {
                f[j][k] = max(f[j][k], f[j - need[i]][k - harm[i]] + 1);
            }
        }
    }
    int k = Vh - 1;
    while (k && f[Vn][k - 1] == f[Vn][Vh - 1]) --k;
    cout << f[Vn][k] << " " << Vh - k; 
}

---

1020. 潜水员(二维费用，至少)

题目描述

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119 

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

第一行有2个整数 $m，n$。它们表示氧，氮各自需要的量。

第二行为整数 $k$ 表示气缸的个数。

此后的 $k$ 行，每行包括$a_i，b_i，c_i$，3个整数。这些各自是：第 $i$ 个气缸里的氧和氮的容量及气缸重量。

输出格式

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围

$1 \le m \le 21$,
$1 \le n \le 79$,
$1 \le k \le 1000$,
$1 \le a_i \le 21$,
$1 \le b_i \le 79$,
$1 \le c_i \le 800$

输入样例：

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119 

输出样例：

249 

算法分析

• 状态表示f[i,j,k]:所有从前i个物品中选,且氧气含量至少是j,氮气含量至少是k的所有选法的气缸重量总和的最小值

• 状态计算：

  • 所有不包含物品i的所有选法：f[i - 1,j,k]

  • 所有包含物品i的所有选法：f[i - 1,j - v1,k - v2]

注意：即使所需要的氧气或者氮气所需的是数量是负数，但其所需数量与0是等价的，因此可以通过所需数量为0来转移

遍历细节

可能很多人会有这样的疑问，二维费用的背包问题的状态转移方程代码如下

for(int j =  V;j >= v;j --)
    for(int k = M;k >= m;k --)
        f[j][k] = max(f[j][k], f[j - v][k - m] + w); 

而本题的状态转移方程代码如下

for(int j = V;j >= 0;j --)
    for(int k = M;k >= 0;k --)
        f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w); 

为什么上面的代码 j只需要遍历到v，k只能遍历到m。而下面的代码 j还需要遍历到0，k还需要遍历到0 ？同时为什么氧气或者氮气所需的是数量是负数时，可以与数量0的状态等价？

解答：对比两题的思路，二维费用的背包问题，求的是不能超过体积V，重量M的情况下，能拿到价值的最大值。而本题是至少需要体积V，重量M的情况下，能拿到价值的最小值。就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如f[3][5]，至少需要3个体积，5个重量，求能拿到价值的最小值，现在只有一个物品，体积是4，重量是4，价值w，它说至少需要3个体积，那么体积是4还是可以用到，只是多了1个体积没用占着而已，不影响其价值。因此若用了这个物品，则变成了求f[max(0,-1)][1] + w = f[0][1] + w，表示体积已经不再需求了，只需要0个体积即可

求最大值最小值初始化总结

二维情况

• 体积至多j，f[i][j] = 0，0 <= i <= n, 0 <= j <= V（只会求价值的最大值）

• 体积恰好j

  • 当求价值的最小值：f[0][0] = 0, 其余是INF
  • 当求价值的最大值：f[0][0] = 0, 其余是-INF

• 体积至少j，f[0][0] = 0，其余是INF（只会求价值的最小值）

一维情况

• 体积至多j，f[i] = 0, 0 <= i <= V（只会求价值的最大值）

• 体积恰好j

  • 当求价值的最小值：f[0] = 0, 其余是INF
  • 当求价值的最大值：f[0] = 0, 其余是-INF

• 体积至少j，f[0] = 0，其余是INF（只会求价值的最小值）

Solution

#include <iostream>
#include <cstring>
using namespace std;
int f[22][80];
int main() {
    int V1, V2, n;
    cin >> V1 >> V2 >> n;
    memset(f, 0x3f ,sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int cost1, cost2, w;
        cin >> cost1 >> cost2 >> w;
        for (int j = V1; j >= 0; --j) {
            for (int k = V2; k >= 0; --k) {
                f[j][k] = min(f[j][k], f[max(0, j - cost1)][max(0, k - cost2)] + w);
            }
        }
    }
    cout << f[V1][V2];
}

---

11. 背包问题求方案数（最优+至多+方案数）

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9 + 7$ 的结果。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示 方案数 模 $10^9 + 7$ 的结果。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 6 

输出样例：

2 

算法分析

体积不超过做法

本题求01背包的最佳方案数，那么定义两个数组：$f[N], cnt[N]$

$f[i]$ 用来存储背包容积为 $i$ 时（背包内物品体积$\leq i$）的最佳方案的总价值，

$cnt[i]$为背包容积为 $i$ 时（背包内物品体积$\leq i$）总价值为最佳的方案数

先初始化所有的 $cnt[i]$ 为 $1$（对应至多时初始化规则），因为背包里什么也不装也是一种方案

求出装新物品时的总价值，与不装新物品时作对比

如果装新物品的方案总价值更大，那么用 $f[j - v] + w$ 来更新 $f[j]$，用 $cnt[j - v]$ 更新 $cnt[j]$

如果总价值相等，那么最大价值的方案数就多了 $cnt[j - v]$ 种

体积恰好等于做法

1. 两个dp数组：
   • $f[j]$ 表示背包容积”恰好”为j时的最大价值和 —— 最优解dp
   • $g[j]$ 表示背包容积”恰好”为j时取最优解的方案数 —— 方案数dp
   • 两个数组通过下标j相对应
2. 最后找到最优解的数值，在$g[j]$里面只要与这个数相等的都是最优方案数
3. 注意：
   • 因为最终不一定占满全部的背包体积，所以最优解不一定是$f[m]$
   • 01背包在这个地方就不一样了，因为01背包就算占不满m的体积到最后也可以转移到$f[m]$中，$f[m]$保留的就是最优解
   • 但是方案数中$g[j]$严格与$f[i]$相对应，必须找出准确的取最优解时的体积
     注意定义的这个**“恰好”**
4. 初始化：
   • $g[0] = 1;//啥都不选也算一种方案$
   • $f[i] = 0;$
   • $f[1\sim n] = -INF;$

求方案数初始化总结

二维情况

• 体积至多j，f[0][i] = 1, 0 <= i <= m，其余是0

• 体积恰好j，f[0][0] = 1, 其余是0

• 体积至少j，f[0][0] = 1，其余是0

一维情况

• 体积至多j，f[i] = 1, 0 <= i <= m，

• 体积恰好j，f[0] = 1, 其余是0

• 体积至少j，f[0] = 1，其余是0

Solution

体积不超过做法

#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], cnt[N];
int main() {
    int n, V;
    cin >> n >> V;
    for (int j = 0; j <= V; ++j) cnt[j] = 1;//不超过时方案数的初始化
    for (int i = 1; i <= n; ++i) {
        int v, w;
        cin >> v >> w;
        for (int j = V; j >= v; --j) {
            int addnew = f[j - v] + w;
            if (addnew == f[j]) cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            if (addnew > f[j]) f[j] = addnew, cnt[j] = cnt[j - v];
        }
    }
    cout << cnt[V];
}

体积恰好等于做法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], cnt[N];
int main() {
    int n, V;
    cin >> n >> V;
    memset(f, 0xc0, sizeof f);
    f[0] = 0, cnt[0] = 1;//体积恰好的时候初始化
    for (int i = 1; i <= n; ++i) {
        int v, w;
        cin >> v >> w;
        for (int j = V; j >= v; --j) {
            int addnew = f[j - v] + w;
            if (addnew == f[j]) cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            if (addnew > f[j]) f[j] = addnew, cnt[j] = cnt[j - v];
        }
    }
    int maxv = 0;
    for (int j = 0; j <= V; ++j) maxv = max(maxv, f[j]);//这里求不超过V的最大值，而f[j]存的是恰好的最大值，这时候f[V]不一定是最大值
    int ans = 0;
    for (int j = 0; j <= V; ++j) 
        if (maxv == f[j]) ans = (ans + cnt[j]) % mod;
    cout << ans;
}

278. 数字组合（恰好+方案数）

题目描述

给定 $N$ 个正整数 $A_1,A_2,…,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，表示 $A_1,A_2,…,A_N$。

输出格式

包含一个整数，表示可选方案数。

数据范围

$1 \le N \le 100$,
$1 \le M \le 10000$,
$1 \le A_i \le 1000$,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2 

输出样例：

3 

算法分析

这是一个典型的 $0 / 1$ 背包模型, $N$ 个正整数就是 $N$ 个物品, $M$ 就是背包的容积。 在外层循环到 $i$ 时（表示从前 $i$ 个数中选), 设 $F[j]$ 表示 “和为 $j$ ” 有多少种方案。 在具体实现中, 只需要把上面代码中求 max 的函数改为求和即可。

• 不选第$i$个数：f[i-1][j]

• 选第$i$个数：f[i-1][j-A[i]]

所以总的方案数为f[i][j] = f[i-1][j] + f[i-1][j-A[i]]

**注意：**因为体积为0时，即j = 0时，是存在一种方案的，所以f[0][0] = 1

f[0][0] = 1;
for(int i=1; i<=n; i++){
    for(int j=0; j<=m; j++){
        f[i][j] = f[i-1][j];
        if(j >= a[i]){
            f[i][j] += f[i-1][j-a[i]];
        }
    }
}

滚动数组优化：

f[0] = 1;
for(int i = 1; i <= n; i++){
    for(int j = m; j >= a[i]; j--){
        //如果j < a[i], f[j]不会更新，还是原来值，为f[i - 1][j]
        f[j] = f[j] + f[j - a[i]];
    }
}

Solution

#include <iostream>
using namespace std;
const int N = 10010;
int f[N], a[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    f[0] = 1;//注意不要漏
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--)
            f[j] += f[j - a[i]];
    cout << f[m] <<endl;
}

---

12. 背包问题求具体方案（字典序最小）

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1 … N$。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1 … N$。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 6 

输出样例：

1 4 

算法分析

分析1

题目要求输出字典序最小的解，假设存在一个包含第1个物品的最优解，为了确保字典序最小那么我们必然要选第一个。

那么问题就转化成从2～N这些物品中找到最优解。之前的$f(i,j)$记录的都是前$i$个物品总容量为$j$的最优解，那么我们现在将$f(i,j)$定义为从第$i$个元素到最后一个元素总容量为$j$的最优解。接下来考虑状态转移：

$f(i,j) = max(f(i + 1,j),f(i+1,j-v[i])+w[i])$

两种情况：

• 第一种是不选第$i$个物品，那么最优解等同于从第$i+1$个物品到最后一个元素总容量为$j$的最优解；

• 第二种是选了第$i$个物品，那么最优解等于当前物品的价值$w[i]$加上从第$i+1$个物品到最后一个元素总容量为$j-v[i]$的最优解。

计算完状态表示后，考虑如何的到最小字典序的解。首先$f(1,m)$肯定是最大价值，那么我们便开始考虑能否选取第1个物品呢。

• 如果$f(1,m) =f(2,m-v[1])+w[1]$，说明选取了第1个物品可以得到最优解。

• 如果$f(1,m) = f(2,m)$，说明不选取第一个物品才能得到最优解。

• 如果$f(1,m)=f(2,m)=f(2,m-v[1])+w[1]$，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

分析2

由于题目要求求字典序最小的方案，因此从1到n中，每个物品有3种情况

• 只能选，则必须选

• 不能选，则必不选

• 可选可不选，则必须选，在前面物品能选的情况下优先选择前面的物品，保证字典序最小

为了满足上述条件，因此需要从第n个物品遍历到第1个物品，求出当前背包的最大总价值f[1][m]

再从第1个物品遍历到第n个物品，其中f[i][j]为当前最优情况，若满足

• f[i][j] == f[i + 1][j],则表示f[i][j]是从f[i + 1][j]状态转移过来的
• f[i][j] == f[i + 1][j - v[i]] + w[i]，则表示f[i][j]是从f[i + 1][j - v[i]]状态转移过来的

从而找出字典序最小的路径方案

完全背包求具体方案 LeetCode 1449. 数位成本和为目标值的最大数字

Solution

#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N], v[N], w[N];
int path[N], idx;
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= V; ++j) {
            f[i][j] = f[i + 1][j];//要判断路径转移，这里不能空间优化一维
            if (j >= v[i]) f[i][j] = max(f[i + 1][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    for (int i = 1, j = V; i <= n; ++i) {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) path[++idx] = i, j -= v[i];
    }
    for (int i = 1; i <= idx; ++i) 
        cout << path[i] << " ";
}

---

完全背包

模型介绍

给定 $N$ 种物品，其中第 $i$ 种物品的体积为 $V_{i}$，价值为 $W_{i}$，并且有无数个。有一容积为 $M$ 的背包，要求选择若干个物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的价值总和最大。

先来考虑使用传统的二维线性 DP 的做法。设 $F[i, j]$ 表示从前 $i$ 种物品中选出了总体积为 $j$ 的物品放入背包，物品的最大价值和。

$$F[i, j]=\max \begin{cases} F[i-1, j] & \text { 尚未选过第 } i \text { 种物品 } \\ F\left[i, j-V_{i}\right]+W_{i} \;,\text { if } j \geq V_{i} & \text { 从第 } i \text { 种物品中选一个 } \end{cases}$$

注意：这里是$F[i][j-V_i]$，完全背包这里是 $i$ ，而0/1背包是 $i-1$

初值: $F[0,0]=0$，其余均为负无穷，目标: $\max _{0 \leq j \leq M}\{F[N][j]\}$ 。

与 $0 / 1$ 背包一样，我们也可以省略 $F$ 数组的 $i$ 这一维。根据我们在 $0 / 1$ 背包中对循环顺序的分析，当采用正序循环时，就对应着每种物品可以使用无限次，也对应着 $F[i, j]=F\left[i, j-V_{i}\right]+W_{i}$ 这个在两个均处于 $i$ 阶段的状态之间进行转移的方程。

int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= m; j++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int j = 0; j <= m; j++) ans = max(ans, f[j]);

---

1023. 买书（恰好+方案数）

题目描述

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式

一个整数 n，代表总共钱数。

输出格式

一个整数，代表选择方案种数。

数据范围

$0 \le n \le 1000$

输入样例1：

20 

输出样例1：

2 

输入样例2：

15 

输出样例2：

0 

输入样例3：

0 

输出样例3：

1 

算法分析

完全背包求方案数，注意恰好等于情况的初始化

Solution

#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int price[] = {0, 10, 20, 50, 100};
int main() {
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; ++i) {
        for (int j = price[i]; j <= n; ++j) {//正序循环
            //f[i][j] = f[i - 1][j] + f[i][j - v] 
            //f[j]未更新前仍是第i-1层状态，对应着f[i - 1][j]
            //正序循环，则f[j - v]在之前已经更新了，已经是第i层状态了,对应着f[i][j - v]
            f[j] += f[j - price[i]];
        }
    }
    cout << f[n];
}

---

279. 自然数拆分（恰好+方案数）

题目描述

给定一个自然数 $N$，要求把 $N$ 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

注意:

• 拆分方案不考虑顺序；
• 至少拆分成 $2$ 个数的和。

求拆分的方案数 $\bmod 2147483648$ 的结果。

输入格式

一个自然数 $N$。

输出格式

输入一个整数，表示结果。

数据范围

$1 \le N \le 4000$

输入样例：

7 

输出样例：

14 

算法分析

这是一个典型的完全背包模型, $1 \sim N - 1$ （因为至少拆成2个数的和）这 $N - 1$ 个自然数构成 $N - 1$ 种物品, 每种物品都可以无限次使用, 背包容积也是 $N$ ，且恰好用完。与上一道例题类似, 本题也是要求方案数, 我们在完全背包程序模板的基础上, 把求 max 的函数改为求和即可。

Solution

#include <iostream>
using namespace std;
const int N = 4010;
long long f[N], mod = 2147483648;
int main() {
    int n; 
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n - 1; ++i) {
        for (int j = i; j <= n; ++j) {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n] << endl;
}

---

1021. 货币系统（恰好+方案数）

题目描述

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式

第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

$n \le 15, m \le 3000$

输入样例：

3 10
1
2
5 

输出样例：

10 

算法分析

(DP,完全背包+方案数) $O(nm)$

可以转化为完全背包问题求方案数：

• 将组成货币的面值数$M$看作背包容量；
• 将每种货币的面值$v$ 看作体积为$v$的物品，每种物品都可以无限次使用；

时间复杂度

背包问题的时间复杂度为$O(nm)$。

Solution

#include <iostream>
using namespace std;
const int N = 20, M = 3010;
long long f[M];
int v[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i];
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = v[i]; j <= m; ++j) {
            f[j] = f[j] + f[j - v[i]]; 
        }
    }
    cout << f[m];
}

---

532. 货币系统

题目描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] × t[i]$ 的和为 $x$。

然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。

例如在货币系统 $n=3, a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。

他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。

他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$，表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。

每组数据的第一行包含一个正整数 $n$。

接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$。

数据范围

$1 \le n \le 100$,
$1 \le a[i] \le 25000$,
$1 \le T \le 20$

输入样例：

2 
4 
3 19 10 6 
5 
11 29 13 19 17 

输出样例：

2
5 

算法分析

定义一个 货币系统 $(n, a)$：一共有 $n$ 种货币，每种货币对应面值为 $a_i$

每种货币可以使用 任意多个，进行线性组合：

$$k = x_1a_1 + x_2a_2 + \cdots + x_na_n，其中 x_i \in Z_0~~i=1,2,\cdots$$

$k$ 为该 货币系统 $(n, a)$ 能够 线性表出 的数值

【注】本题的 线性表出 对于 系数的要求 和 线性代数 中的 线性表出 是不一样的

本题的系数必须是 非负整数

---

定义：

$$(n, a) 和 (m, b) 等价 \Leftrightarrow \forall k \in Z^+， \begin{cases} k如果能被a线性表出，则k也能被b线性表出\\ k如果不能被a线性表出，则k也不能被b线性表出 \end{cases}$$

现给定 货币系统 $(n, a)$，求一个 等价 的 货币系统 $(m, b)$ ，要求 $m$ 尽可能最小

分析

$n$ 种货币，每种货币可以使用 无穷多个

通过这些信息，我们可以初步识别该题目是一个 完全背包 的变种题目

接着我们需要挖掘一下题目里的性质：

学过 线性代数 的同学可以无视这一部分，跳到下面的分割线继续看

研究 货币系统 $(n, a)$ ，如果存在 $a_j$ 可以被 $a$ 中其他的向量 线性表出：

$$a_j = \sum_{i\ne j} c_ia_i$$

则 $a_j$ 在这个货币系统中是 无效的 (所有线性表示中需要用到$a_j$的项，都可以用 $\sum_{i\ne j} c_ia_i$ 代替)

因此，我们需要求出 货币系统 $(n, a)$ 的 最大无关向量组，即任意 $a_i$ 都不能被其他向量 线性表出

---

如何求向量组 $(a_1,a_2,\cdots,a_n)$ 的 最大无关向量组

我们可以利用到 数论 中 埃式筛法 的思想：

对于一个 无效的 元素 $a_i$，他只会被 小于 他的元素的 线性组合 表出，满足该要求的 $a_i$ 就要被 筛掉

所以我们要先 排序

而我们在做 完全背包 的时候，需要求出所有恰好能被前 $i$ 个物品选出的体积的方案

即就是在 完全背包 求方案数的过程中，统计那些 初始不能被满足 的物品体积 个数

这就是我们在 1021. 货币系统 中所使用的 DP模型

那一题我们求解的是方案数，这题稍微改一下，改成这种方案能否被满足即可，或者相当于方案数为0

---

算法流程：

这题是一道类似线性代数问题，但系数为正整数
求解一个向量组的秩(最大无关向量组的向量个数)
但是代码写起来就是一个模拟筛的过程

• 排序
• 从小到大，先查看当前数有没有被晒掉
  • 如果没有就把它加入到最大无关向量组中，并把他以及他和此前的硬币的线性组合都筛掉
  • 如果已经被筛掉，就跳过，防止重复筛
• 即在完全背包求方案数的过程中，统计那些初始没有方案数的物品，这样就变成一个完全背包问题了

---

Solution

方案数 = 0

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
int f[110][N];
int a[110];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        
        sort(a + 1, a + 1 + n);
  		//完全背包求方案数
        int m = a[n];
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= a[i]) f[i][j] += f[i][j - a[i]];
            }
        }
        
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (f[i - 1][a[i]] == 0) ++ans;//如果当前数不能被前面的数组合
        }
        cout << ans << endl;
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
int f[N];
int a[110];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        
        sort(a + 1, a + 1 + n);
        
        int m = a[n], ans = 0;
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (f[a[i]] == 0) ++ans;//这里的f[a[i]]表示f[i - 1][a[i]]
            for (int j = a[i]; j <= m; ++j) {
                f[j] += f[j - a[i]];
            }
        }
        cout << ans << endl;
    }
}

筛除

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010;
bool f[N];
int a[110];//体积和价值相等都是a[i]
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        
        sort(a + 1, a + 1 + n);//一定要注意，如果下标从1开始，排序的时候要注意加1
        
        int m = a[n], ans = 0;
        memset(f, 0, sizeof f);
        f[0] = true;
        for (int i = 1; i <= n; ++i) {
            //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的,并跳过
            if (f[a[i]] == true) continue;
            //如果没有被筛掉，则把它加入最大无关向量组
            ++ans;
            //筛掉当前最大无关向量组能线性表示的体积
            for (int j = a[i]; j <= m; ++j) {
                f[j] |= f[j - a[i]]; //相当于f[j] = f[j] || f[j - a[i]]
            }
        }
        cout << ans << endl;
    }
}

---

280. 陪审团

题目描述

在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。

陪审团是由法官从公民中挑选的。

法官先随机挑选 $N$ 个人（编号 $1,2…,N$）作为陪审团的候选人，然后再从这 $N$ 个人中按照下列方法选出 $M$ 人组成陪审团。

首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 $0$ 到 $20$ 之间。

第 $i$ 个人的得分分别记为 $p[i]$ 和 $d[i]$。

为了公平起见，法官选出的 $M$ 个人必须满足：辩方总分 $D$ 和控方总分 $P$ 的差的绝对值 $|D-P|$ 最小。

如果选择方法不唯一，那么再从中选择辨控双方总分之和 $D+P$ 最大的方案。

求最终的陪审团获得的辩方总分 $D$、控方总分 $P$，以及陪审团人选的编号。

注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含两个整数 $p[i]$ 和 $d[i]$。

每组测试数据之间隔一个空行。

当输入数据 $N=0，M=0$ 时，表示结束输入，该数据无需处理。

输出格式

对于每组数据，第一行输出 Jury #C，$C$ 为数据编号，从 $1$ 开始。

第二行输出 Best jury has value P for prosecution and value D for defence:，$P$ 为控方总分，$D$ 为辩方总分。

第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。

每组数据输出完后，输出一个空行。

数据范围

$1 \le N \le 200$,
$1 \le M \le 20$
$0 \le p[i], d[i] \le 20$

输入样例：

4 2
1 2
2 3
4 1
6 2
0 0 

输出样例：

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
 2 3 

算法分析

这是一道具有多个“体积维度” 的 0/1 背包问题。把 $N$ 个候选人看作 $N$ 个物品, 那么每个物品有如下三种 “体积” :

1. “人数” , 每个 “候选人” 的 “人数” 都是 1, 最终要填满容积为 $M$ 的背包。

2. “辡方得分”, 即㦚方给该候选人打的分数 $a[i]$, 一个 $0 \sim 20$ 的整数

3. “控方得分”, 即控方给该候选人打的分数 $b[i]$, 一个 $0 \sim 20$ 的整数。

因此, 我们依次考虑每个候选人是否选入评审团, 当外层循环到阶段 $i$ 时, 表示已经考虑了前 $i$ 个候选人的入选情况, 此时用 Boolean 数组 $F[j, d, p]$ 表示已有 $j$ 人 被选入评审团, 当前辩方总分为 $d 、$ 控方总分为 $p$ 的状态是否可行。

$$F[j, d, p]=F[j, d, p] \text { or } F[j-1, d-a[i], p-b[i]]$$

初值: $F[0,0,0]=$ true, 其余均为 false。

目标: 找到一个状态 $F[M, d, p]$, 满足 $F[M, d, p]=$ true, 并且 $|d-p|$ 尽量小, $|d-p|$ 相同时 $d+p$ 尽量大。

上述算法没有很好地利用背包 “价值” 这一维度, 还有很大的优化空间。实际上, 我们可以把每个候选人㦚、控双方得分的差 $a[i]-b[i]$ 作为该物品的 “体积”之一, 把辩、控双方得分的和作为该物品的价值。

当外层循环到 $i$ 时, 设 $F[j, k]$ 表示已经在前 $i$ 个候选人中选出了 $j$ 个, 此时辡 方总分与控方总分的差为 $k$ 时, 辩方总分与控方总分的和的最大值。

$$F[j, k]=\max (F[j, k], F[j-1, k-(a[i]-b[i])]+a[i]+b[i])$$

初值: $F[0,0]=0$, 其余均为负无穷。

目标: 找到一个状态 $F[M, k]$, 满足 $|k|$ 尽量小, 当 $|k|$ 相同时 $F[M, k]$ 尽量大。

在转移中, 注意对 $j$ 这一维执行倒序循环, 即可保证每个候选人只会被选一次, 符合 $0 / 1$ 背包的特征。

本题还要求输出评审团人选的具体方案。我们采用记录转移路径的方法, 额外建立一个数组 $D$, 其中 $D[i, j, k]$ 表示外层循环执行到 $i$ 时, 状态 $F[j, k]$ 的最大值是选了哪一名候选人而得到的。这里我们必须采用三维数组, 否则后续对 $i$ 的循环可能会覆盖之前 $D[j, k]$ 保存的值。求出最优解后, 可以沿着数组 $D$ 记录的转移路径, 递归得到方案。设 $last =D[i, j, k]$, 不断从状态 $(i, j, k)$ 递归到 $(last -1, j-1, k-(a[last]-b[last]))$, 直至 $j=0$ 。递归过程中所有的 $last$ 值就构成了评审团的人选。

Solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int f[25][805]; // 前i个人，选了j个，辩方总分与控方总分的差为k=-400~400（平移到0~800）
int d[205][25][805]; // 记路径还是要三维，不然后面的更新可能会覆盖掉之前的记录
int n, m, a[205], b[205], suma, sumb, T;
vector<int> c;

void get_path(int i, int j, int k) {
	if (j == 0) return;
	int last = d[i][j][k];
	get_path(last - 1, j - 1, k - (a[last] - b[last]));
	c.push_back(last);
	suma += a[last], sumb += b[last];
}

int main() {
	while (cin >> n >> m && n) {
		for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
		memset(f, 0xcf, sizeof(f)); // -INF
		f[0][400] = 0; // f[0][0]第三维平移400
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) // 不选i
				for (int k = 0; k <= 800; k++) d[i][j][k] = d[i - 1][j][k];
			for (int j = m; j; j--) // 选i
				for (int k = 0; k <= 800; k++) {
					if (k - (a[i] - b[i]) < 0 || k - (a[i] - b[i]) > 800) continue; // 超出范围
					if (f[j][k] < f[j - 1][k - (a[i] - b[i])] + a[i] + b[i]) {
						f[j][k] = f[j - 1][k - (a[i] - b[i])] + a[i] + b[i];
						d[i][j][k] = i;
					}
				}
		}
		int ans = 0;
		for (int k = 0; k <= 400; k++) {
			if (f[m][400 + k] >= 0 && f[m][400 + k] >= f[m][400 - k]) {
				ans = k + 400;
				break;
			}
			if (f[m][400 - k] >= 0) {
				ans = 400 - k;
				break;
			}
		}
		c.clear();
		suma = sumb = 0;
		get_path(n, m, ans);
		printf("Jury #%d\n", ++T);
		printf("Best jury has value %d for prosecution and value %d for defence:\n", suma, sumb);
		for (int i = 0; i < c.size(); i++) printf(" %d", c[i]);
		printf("\n\n");
	}
}

---

多重背包

模型介绍

给定 $N$ 种物品, 其中第 $i$ 种物品的体积为 $V_{i}$, 价值为 $W_{i}$, 并且有 $C_{i}$ 个。有一 容积为 $M$ 的背包, 要求选择若千个物品放入背包, 使得物品总体积不超过 $M$ 的前提 下, 物品的价值总和最大。

直接拆分法

求解多重背包问题最直接的方法是把第 $i$ 种物品看作独立的 $C_{i}$ 个物品, 转化为共有 $\sum_{i=1}^{N} C_{i}$ 个物品的 0/1 背包问题进行计算, 时间复杂度为 $O\left(M * \sum_{i=1}^{N} C_{i}\right)$ 。该算法把每种物品拆成了 $C_{i}$ 个, 效率较低。

unsigned int f[MAX_M+1];
memset(f, 0xcf, sizeof(f)); // -INF
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int k = 1; k <= c[i]; k++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
for (int i = 0; i <= m; i++)
    ans = max(ans, f[i]);

#include <iostream>
using namespace std;
const int N = 110;
int f[N];
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; ++k) {
        //上面两重循环将每种物品拆分成多个独立的物品
            //这里循环对这些独立物品进行0/1背包求解
            for (int j = V; j >= v; --j)
                f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[V];
}

#include <iostream>
using namespace std;
const int N = 110;
int f[N];
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = V; j >= v; --j) {
            for (int k = 1; k <= s && j >= k * v; ++k) {
                //选多少个
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[V];
}

---

二进制拆分法

解释1

众所周知, 从 $2^{0}, 2^{1}, 2^{2}, \cdots, 2^{k-1}$ 这 $k$ 个 2 的整数次幂中选出若干个相加, 可以 表示出 $0 \sim 2^{k}-1$ 之间的任何整数。进一步地, 我们求出满足 $2^{0}+2^{1}+\cdots+2^{p} \leq C_{i}$ 的最大的整数 $p$, 设 $R_{i}=C_{i}-2^{0}-2^{1}-\cdots-2^{p}$, 那么:

1. 根据 $p$ 的最大性, 有 $2^{0}+2^{1}+\cdots+2^{p+1}>C_{i}$, 可推出 $2^{p+1}>R_{i}$, 因此 $2^{0}, 2^{1}, \cdots, 2^{p}$ 选出若干个相加可以表示出 $0 \sim R_{i}$ 之间的任何整数。
2. 从 $2^{0}, 2^{1}, \cdots, 2^{p}$ 以及 $R_{i}$ 中选出若干个相加, 可以表示出 $R_{i} \sim R_{i}+2^{p+1}-1$ 之间的任何整数, 而根据 $R_{i}$ 的定义, $R_{i}+2^{p+1}-1=C_{i}$, 因此 $2^{0}, 2^{1}, \cdots, 2^{p}, R_{i}$ 选出若 干个相加可以表示出 $R_{i} \sim C_{i}$ 之间的任何整数。

综上所述, 我们可以把数量为 $C_{i}$ 的第 $i$ 种物品拆成 $p+2$ 个物品, 它们的体积分别为:

$$2^{0} * V_{i}, \;2^{1} * V_{i},\; \cdots, \;2^{p} * V_{i},\; R_{i} * V_{i}$$

这 $p+2$ 个物品可以凑成 $0 \sim C_{i} * V_{i}$ 之间所有能被 $V_{i}$ 整除的数, 并且不能凑成大于 $C_{i} * V_{i}$ 的数。这等价于原问题中体积为 $V_{i}$ 的物品可以使用 $0 \sim C_{i}$ 次。该方法仅把每种物品拆成了 $O\left(\log C_{i}\right)$ 个, 效率较高。

解释2

利用二进制的思想, 我们把第 $i$ 种物品换成若干件物品, 使得原问题中第 $i$ 种物品可取的每种策略「取 $0\cdots s_{i}$ 件」均能等价于取若干件代换以后的物品。 另外, 取超过 $s_{i}$ 件的策略必不能出现。

方法是：将第 $i$ 种物品分成若干件 01 背包中的物品, 其中每件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。

• 令这些系数分别为 $1,2^1,2^{2}, \cdots ,2^{k-1}, s_{i}-2^{k}+1$, 且 $k$ 是满足 $1+2^1+2^2+\cdots+2^{k-1}=2^{k}-1\leq s_{i}$ 的最大整数，即 $k=\lfloor \log_2(s_i+1) \rfloor$ 。

• 分成的这几件物品的系数和为 $s_{i}$, 表明不可能取多于 $s_{i}$ 件的第 $i$ 种物品。

• 另外 这种方法也能保证对于 $0 \ldots s_{i}$ 间的每一个整数，均可以用若干个系数的和表示。这里算法正确性的证明可以分 $0 \ldots 2^{k-1}$ 和 $2^{k} \cdots s_{i}$ 两段来分别讨论得出。

这样就将第 $i$ 个物品分成了 $O(\log{s_i})$ 个物品，复杂度降为 $O(V\sum_{i=1}^N\log{s_i})$

代码实现

#include <iostream>
#include <vector>
using namespace std;
int f[2010];
vector<pair<int,int>> goods;
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        //二进制拆分,注意s -= k
        for (int k = 1; k <= s; s -= k, k *= 2) goods.push_back({k * v, k * w});
        if (s) goods.push_back({s * v, s * w});
    }
    //01背包求解
    for (int i = 0; i < goods.size(); ++i) {
        int v = goods[i].first, w = goods[i].second;
        for (int j = V; j >= v; --j) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[V];
}

---

单调队列优化

使用单调队列优化的动态规划算法求解多重背包问题, 时间复杂度可以进一步降 低到 $O(N M)$, 与 $0 / 1$ 背包和完全背包中 DP 算法的效率相同。

---

1019. 庆功会

题目描述

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

输入格式

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

输出格式

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

数据范围

$n \le 500, m \le 6000$,
$v \le 100, w \le 1000, s \le 10$

输入样例：

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1 

输出样例：

1040 

算法分析

Solution

#include <iostream>
using namespace std;
int f[6010];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= v; --j) {
            for (int k = 0; k <= s && k * v <= j; ++k) {
                f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[m];
}

---

281. 硬币

题目描述

给定 $N$ 种硬币，其中第 $i$ 种硬币的面值为 $A_i$，共有 $C_i$ 个。

从中选出若干个硬币，把面值相加，若结果为 $S$，则称“面值 $S$ 能被拼成”。

求 $1 \sim M$ 之间能被拼成的面值有多少个。

输入格式

输入包含多组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$。

第二行包含 $2N$ 个整数，分别表示 $A_1,A_2,…,A_N$ 和 $C_1,C_2,…,C_N$。

当输入用例 $N=0，M=0$ 时，表示输入终止，且该用例无需处理。

输出格式

每组用例输出一个结果，每个结果占一行。

数据范围

$1 \le N \le 100$,
$1 \le M \le 10^5$,
$1 \le A_i \le 10^5$,
$1 \le C_i \le 1000$

输入用例：

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0 

输出用例：

8
4 

算法分析

Solution

---

分组背包

模型介绍

给定 $N$ 组物品, 其中第 $i$ 组有 $C_{i}$ 个物品。第 $i$ 组的第 $j$ 个物品的体积为 $V_{i j}$, 价值为 $W_{ij}$ 。有一容积为 $M$ 的背包, 要求选择若干个物品放入背包, 使得每组至多选择一个物品并且物品总体积不超过 $M$ 的前提下, 物品的价值总和最大。

仍然先考虑原始线性 DP 的做法。为了满足 “每组至多选择一个物品”, 很自然的想法就是利用 “阶段” 线性增长的特征, 把 “物品组数” 作为 DP 的 “阶段”, 只要使用了一个第 $i$ 组的物品, 就从第 $i$ 个阶段的状态转移到第 $i+1$ 个阶段的状态。设 $F[i, j]$ 表示从前 $i$ 组中选出总体积为 $j$ 的物品放入背包, 物品的最大价值和。

$$F[i, j]=\max \begin{cases} F[i-1, j] & \text { 不选第 } i \text { 组的物品 } \\F\left[i-1, j-V_{i k}\right]+W_{i k} \;,\;1 \leq k \leq C_{i}& \text { 选第 } i \text { 组的某个物品 } k \end{cases}$$

与前面几个背包模型一样, 我们可以省略掉 $F$ 数组的第一维, 用 $j$ 的倒序循环来控制 “阶段 $i$ " 的状态只能从 “阶段 $i-1$ "转移而来。

memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; i++)
    for (int j = m; j >= 0; j--)//倒序循环
        for (int k = 1; k <= c[i]; k++)
            if (j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

除了倒序循环 $j$ 之外, 请读者格外留意, 对于每一组内 $c[i]$ 个物品的循环 $k$ 应该放在 $j$ 的内层。从背包的角度看, 这是因为每组内至多选择一个物品, 若把 $k$ 置于 $j$ 的外层, 就会类似于多重背包, 每组物品在 $F$ 数组上的转移会产生累积, 最终可以选择超过 1 个物品。从动态规划的角度, $i$ 是 “阶段”, $i$ 与 $j$ 共同构成 “状态”, 而 $k$ 是 “决策”一一在第 $i$ 组内使用哪一个物品, 这三者的顺序绝对不能混淆。

另外, 分组背包是许多树形 DP 问题中状态转移的基本模型。

在本节中, 我们介绍了 0/1 背包、完全背包、多重背包和分组背包。除了以传统的线性 DP 求解之外, 我们还尽量缩减了空间复杂度, 省去了 “阶段” 的存储, 用适当的循环顺序控制状态在原有基础上直接转移和累积。请读者不要只把正确的循环顺序记住了事, 务必要理解清楚其中的本质和内在联系。

---

1013. 机器分配

题目描述

总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。

各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。

问：如何分配这M台设备才能使国家得到的盈利最大？

求出最大盈利值。

分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

输入格式

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；

接下来是一个N*M的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。

输出格式

第一行输出最大盈利值；

接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。

答案不唯一，输出任意合法方案即可。

数据范围

$1 \le N \le 10$,
$1 \le M \le 15$

输入样例：

3 3
30 40 50
20 30 50
20 25 30 

输出样例：

70
1 1
2 1
3 1 

算法分析

本题乍一看很像是 背包DP，为了转换成 背包DP 问题，我们需要对里面的一些叙述做出 等价变换

每家公司 我们可以看一个 物品组，又因为 每家公司 最终能够被分配的 机器数量 是固定的

因此对于分给第 $i$ 个 公司 的不同 机器数量 可以分别看作是一个 物品组 内的 物品

该 物品 $k$ 的含义：分给第 $i$ 个 公司 $k$ 台机器

该 物品 $k$ 的体积：$k$

该 物品 $k$ 的价值：$w_{ik}$

于是，本题就转换成了一个 分组背包问题

初始状态 ：f[0][0]

目标状态 ：f[N][M]

动态规划求状态转移路径从 图论 角度思考的方法

动态规划 本质是在一个 拓扑图 内找最短路

我们可以把每个 状态f[i][j]看作一个 点，状态的转移 看作一条 边，把 状态的值 理解为 最短路径长

具体如下图所示：

对于 点 f[i][j] 来说，他的 最短路径长 是通过所有到他的 边 更新出来的

更新 最短路 的 规则 因题而异，本题的 更新规则 是 $f(i,j)=\max{f(i-1,j-v_i)+w_i}$

最终，我们会把从 初始状态（起点）到 目标状态 （终点）的 最短路径长 更新出来

随着这个更新的过程，也就在整个 图 中生成了一颗 最短路径树

该 最短路径树 上 起点 到 终点 的 路径 就是我们要求的 动态规划的状态转移路径

如下图所示：

那么 动态规划求状态转移路径 就变成了在 拓扑图 中找 最短路径 的问题了

可以直接沿用 最短路 输出路径的方法就可以找出 状态的转移

Solution

#include <iostream>
using namespace std;
const int N = 20;
int f[N][N], w[N][N], path[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) cin >> w[i][j];
    
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            for (int k = 0; k <= j; ++k) {//k = 0 不选第i组
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
            }
        }
    }
    cout << f[n][m] << endl;
    
    for (int i = n, j = m; i >= 1; --i) {
        for (int k = 1; k <= j; ++k) 
            if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
                path[i] = k, j -= k;
                break;
            }
    }
    for (int i = 1; i <= n; ++i) {
        cout << i << " " << path[i] << endl;
    }
}

---

487. 金明的预算方案(有依赖)

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件。

每个主件可以有0个、1个或2个附件。

附件不再有从属于自己的附件。

金明想买的东西很多，肯定会超过妈妈限定的N元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是10元的整数倍）。

他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为$j_1，j_2，…，j_k$，则所求的总和为：

$v[j_1] * w[j_1]+v[j_2] * w[j_2]+…+v[j_k] * w[j_k]$ （其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式

输入文件的第1行，为两个正整数，用一个空格隔开：N m，其中N表示总钱数，m为希望购买物品的个数。

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q，其中v表示该物品的价格，p表示该物品的重要度（1~5），q表示该物品是主件还是附件。

如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号。

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

数据范围

$N < 32000, m < 60, v < 10000$

输入样例：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0 

输出样例：

2200 

算法分析

(DP,分组背包问题) $O(Nm)$

可以将每个主件及其附件看作一个物品组，记主件为 $p$，两个附件为 $a, b$，则最多一共有4种组合：

1. $p$
2. $p, a$
3. $p, b$
4. $p, a, b$

这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。

在枚举四种组合时可以使用二进制的思想，可以简化代码。

时间复杂度

分组背包的时间复杂度是 物品总数 * 总体积，因此总时间复杂度是 $O(Nm)$。

Solution

#include <iostream>
#include <vector>
using namespace std;
const int N = 70, M = 32010;
int f[M];
pair<int,int> master[N];
vector<pair<int,int>> attachment[N];
int main() {
    int n, m;
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        int v, p, q;
        cin >> v >> p >> q;
        if (q == 0) master[i] = {v, v * p};
        else attachment[q].push_back({v, v * p});
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= 0; --j) {
            for (int u = 0; u < 1 << attachment[i].size(); ++u) {
                int v = master[i].first, w = master[i].second;
                for (int k = 0; k < attachment[i].size(); ++k) {
                    if (u >> k & 1) {
                        v += attachment[i][k].first;
                        w += attachment[i][k].second;
                    }
                }
                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
        }
    }
    cout << f[m];
}

综合运用

7. 混合背包问题

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 $s_i$ 次（多重背包）；

每种体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

• $s_i = -1$ 表示第 $i$ 种物品只能用1次；
• $s_i = 0$ 表示第 $i$ 种物品可以用无限次；
• $s_i >0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N, V \le 1000$
$0 \lt v_i, w_i \le 1000$
$-1 \le s_i \le 1000$

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2 

输出样例：

8 

算法分析

01背包与完全背包的混合

考虑到 01 背包和完全背包中给出的伪代码只有一处不同, 故如果只有两类物品：

• 一类物品只能取一次

• 另一类物品可以取无限次,

那么只需在对每个物品应用转移方程时, 根据物品的类别选用顺序或逆序的循环即可, 复杂度是 $O(V N)$ 。

伪代码如下:

$$\begin{aligned} &\text { for } i \leftarrow 1 \text { to } N \\ &\text { if 第 } i \text { 件物品属于 } 01 \text { 背包 } \\ &\qquad \text { for } v \leftarrow V \text { to } C_{i} \\ & \qquad \qquad F[v] \leftarrow \max \left(F[v], F\left[v-C_{i}\right]+W_{i}\right)\\ &\text { else if } \text { 第 } i \text { 件物品属于完全背包 } \\ & \qquad \text { for } v \leftarrow C_{i} \text { to } V \\ & \qquad \qquad F[v] \leftarrow \max \left(F[v], F\left[v-C_{i}\right]+W_{i}\right) \end{aligned}$$

再加上多重背包

如果再加上最多可以取有限次的多重背包式的物品, 那么利用单调队列, 也可以给出均摧 $O(V N)$ 的解法。

但如果不考虑单调队列算法的话, 用将每个这类物品分成 $O\left(\log M_{i}\right)$ 个 01 背包的物 品的方法也已经很优了。

最清晰的写法是分别调用这三种问题的三个过程。

$$\begin{aligned} &\text { for } i \leftarrow 1 \text { to } N \\ &\qquad \text { if 第 } i \text { 件物品属于 } 01 \text { 背包 } \\ &\qquad \qquad \text { ZeroOnePack }\left(F, C_{i}, W_{i}\right) \\ &\qquad \text { else if 第 } i \text { 件物品属于完全背包 } \\ &\qquad \qquad \text { CompletePack }\left(F, C_{i}, W_{i}\right) \\ &\qquad \text { else if 第 } i \text { 件物品周于多重背包 } \\ &\qquad \qquad \text { MultiplePack }\left(F, C_{i}, W_{i}, N_{i}\right) \end{aligned}$$

Solution

#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == -1) {// 01背包
            for (int j = m; j >= v; --j) 
                f[j] = max(f[j], f[j - v] + w);
        }
        if (s == 0) { //完全背包
            for (int j = v; j <= m; ++j) 
                f[j] = max(f[j], f[j - v] + w);
        } 
        if (s > 0) { //多重背包
            for (int k = 1; k <= s; s -= k, k *= 2) {
                for (int j = m; j >= k * v; --j) 
                    f[j] = max(f[j], f[j - k * v] + k * w);
            }
            if (s) {
                for (int j = m; j >= s * v; --j) 
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m];
}

#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        s = abs(s);//将01背包合并到多重背包问题求解
        if (s == 0) 
            for (int j = v; j <= m; ++j) f[j] = max(f[j], f[j - v] + w);
        if (s > 0) {
            for (int k = 1; k <= s; s -= k, k *= 2) 
                for (int j = m; j >= k * v; --j) f[j] = max(f[j], f[j - k * v] + k * w);
            if (s) 
                for (int j = m; j >= s * v; --j) f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }
    cout << f[m];
}

---

10. 有依赖的背包问题

题目描述

有 $N$ 个物品和一个容量是 $V$ 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 $i$，体积是 $v_i$，价值是 $w_i$，依赖的父节点编号是 $p_i$。物品的下标范围是 $1 … N$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 $N，V$，用空格隔开，分别表示物品个数和背包容量。

接下来有 $N$ 行数据，每行数据表示一个物品。
第 $i$ 行有三个整数 $v_i, w_i, p_i$，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 $p_i = -1$，表示根节点。 数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

数据范围

$1 \le N, V \le 100$
$1 \le v_i, w_i\le 100$

父节点编号范围：

• 内部结点：$1 \le p_i \le N$;
• 根节点 $p_i = -1$;

输入样例

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2 

输出样例：

11 

算法分析

$1.1$ 简化的问题

这种背包问题的物品间存在某种 “依赖” 的关系。也就是说，物品 $i$ 依赖于物品 $j$，表示若选物品 $i$，则必须选物品 $j$ 。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖; 另外，没有某件物品同时依赖多件物品。

$1.2$ 算法

这个问题由 NOIP2006 中 “金明的预算方案”一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为 “主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。

按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非 常多，包括: 一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选 泽两个附件…无法用状态转移方程来表示如此多的策略。事实上，设有 $n$ 个附件，则策略有 $2^{n}+1$ 个，为指数级。

考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于分组背包问题中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。

再考虑对每组内的物品应用优化。我们可以想到，对于第 $k$ 个物品组中的 物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，可以对主件 $k$ 的 “附件集合” 先进行一次 01 背包，得到费用依次为 $0 \ldots V-C_{k}$ 所有这些值时相应的最 大价值 $F_{k}\left[0 \ldots V-C_{k}\right]$ 。那么，这个主件及它的附件集合相当于 $V-C_{k}+1$ 个物品的 物品组，其中费用为 $v$ 的物品的价值为 $F_{k}\left[v-C_{k}\right]+W_{k}, v$ 的取值范围是 $C_{k} \leq v \leq V_{\text {。 }}$

也就是说，原来指数级的策略中，有很多策略都是冗余的，通过一次 01 背包后， 等主件 $k$ 及其附件转化为 $V-C_{k}+1$ 个物品的物品组，就可以直接应用分组背包问题的算法解决问题了。

$1.3$ 较一般的问题

更一般的问题是：依赖关系以图论中 “森林”的形式给出。也就是说，主件的附件 仍然可以具有自己的附件集合。限制只是每个物品最多只依赖于一个物品（只有一个主 件）且不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同 的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的 01 背包中的物品 了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题 解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。

事实上，这是一种树形动态规划，其特点是，在用动态规划求每个父节点的属性之 前，需要对它的各个儿子的属性进行一次动态规划式的求值。这已经触及到了“泛化物品”的思想。看完泛化物品后，你会发现这个 “依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

$1.4$ 小结

通过引入 “物品组” 和“依赖”的概念可以加深对金明的预算方案这题的理解，还可以 解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主 件又作附件，每个主件最多有两个附件，可以发现一个主件和它的两个附件等价于一个 由四个物品组成的物品组，这便揭示了问题的某种本质。

$2.1$ 泛化物品定义

考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的 费用而变化。这就是泛化物品的概念。

更严格的定义之。在背包容量为 $V$ 的背包问题中，泛化物品是一个定义域为 $0 \ldots V$ 中的整数的函数 $h$，当分配给它的费用为 $v$ 时，能得到的价值就是 $h(v)$ 。

这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组 $h[0 \ldots V]$，给它 费用 $v$，可得到价值 $h[v]$ 。

一个费用为 $c$ 价值为 $w$ 的物品，如果它是 01 背包中的物品，那么把它看成泛化物 品，它就是除了 $h(c)=w$ 外，其它函数值都为 0 的一个函数。如果它是完全背包中的 物品，那么它可以看成这样一个函数，仅当 $v$ 被 $c$ 整除时有 $h(v)=w \cdot \frac{v}{c}$，其它函数值 均为 0 。如果它是多重背包中重复次数最多为 $m$ 的物品，那么它对应的泛化物品的函 数有 $h(v)=w \cdot \frac{v}{c}$ 仅当 $v$ 被 $c$ 整除且 $\frac{v}{c} \leq n$，其它情况函数值均为 0 。

一个物品组可以看作一个泛化物品 $h_{\circ}$ 对于一个 $0 \ldots V$ 中的 $v$，若物品组中不存在 费用为 $v$ 的物品，则 $h(v)=0$，否则 $h(v)$ 取值为所有费用为 $v$ 的物品的最大价值。 6 中 每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。

$2.2$ 泛化物品的和

如果给定了两个泛化物品 $h$ 和 $l$，要用一定的费用从这两个泛化物品中得到最大的 价值，这个问题怎么求呢? 事实上，对于一个给定的费用 $v$，只需枚举将这个费用如何 分配给两个泛化物品就可以了。同样的，对于 $0 \ldots V$ 中的每一个整数 $v$，可以求得费用 $v$ 分配到 $h$ 和 $l$ 中的最大价值 $f(v)$ 。也即

$$f(v)=\max \{h(k)+l(v-k) \mid 0 \leq k \leq v\}$$

可以看到，这里的 $f$ 是一个由泛化物品 $h$ 和 $l$ 决定的定义域为 $0 \ldots \mathrm{V}$ 的函数，也就 是说，$f$ 是一个由泛化物品 $h$ 和 $l$ 决定的泛化物品。

我们将 $f$ 定义为泛化物品 $h$ 和 $l$ 的和： $h 、 l$ 都是泛化物品，若函数 $f$ 满足以上 关系式，则称 $f$ 是 $h$ 与 $l$ 的和。泛化物品和运算的时间复杂度取决于背包的容量，是 $O\left(V^{2}\right)$ 。
由泛化物品的定义可知：在一个背包问题中，若将两个泛化物品代以它们的和，不 影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过 程也就是求所有这些泛化物品之和的过程。若问题的和为 $s$，则答案就是 $s(0 \ldots V)$ 中 的最大值。

$2.3$ 背包问题的泛化物品

一个背包问题中，可能会给出很多条件，包括每种物品的费用、价值等属性，物品 之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说，给定了 所有条件以后，就可以对每个非婴整数 $v$ 求得：若背包容量为 $v$，将物品装入背包可得 到的最大价值是多少，这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物 品一一或者说问题所对应的一个定义域为非败整数的函数一一包含了关于问题本身的高 度浓缩的信息。一般而言，求得这个泛化物品的一个子定义域（例如 $0 \ldots V$ ）的值之后，就可以根据这个函数的取值得到背包问题的最终答案。

综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问 题的泛化物品。而求解某个泛化物品的一种常用方法就是将它表示为若干泛化物品的和 矨后求之。

Solution

f[u][j]：在以节点u为根的子树中进行选择，且体积不超过j，所能获得的最大价值，节点u必被选择

#include <iostream>
#include <vector>
using namespace std;
const int N = 110;
int f[N][N];
vector<int> sons[N];
int v[N], w[N], p[N];
int n, m;
void dfs(int u) {
    //初始化，因为节点u必被选择，所以初始化将节点u的价值加上
    for (int j = m; j >= v[u]; --j) f[u][j] = w[u];
    //循环物品组
    //节点u的每一个子树都相当于一个物品组
    for (int i = 0; i < sons[u].size(); ++i) {
        int son = sons[u][i];
        dfs(son);   
		//循环体积
        for (int j = m; j >= v[u]; --j)
            //循环决策
            //k表示分配给该子树的可用体积
            //相当于该物品组第k个物品，体积为k，价值为f[son][k]
            for (int k = 0; k <= j - v[u]; ++k) 
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }
}
int main() {
    cin >> n >> m;
    int root;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i] >> p[i];
        if (p[i] == -1) root = i;
        else sons[p[i]].push_back(i);
    }
    dfs(root);
    cout << f[root][m];
}