背包问题是一类经典的动态规划问题，是一种组合优化的 NP 完全问题。NP 完全问题无多项式时间复杂度的解法，但是可以利用动态规划，以伪多项式时间复杂度求解。
问题描述：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
背包问题最要紧的是 01 背包和完全背包。其余背包面试几乎不会问，主要是竞赛的，Leetcode 甚至木得多重背包的题目。
0-1 背包问题
问题描述：有 $N$ 件物品和一个容量为 $C$ 的背包。第i件物品的体积是 $c[i]$ ，价值是 $w[i]$，求解将哪些物品装入背包可使价值总和最大
特点：每种物品仅有一件，可以选择放或不放
子问题定义状态：$dp[i][j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值
状态转移方程：
$$
dp[i][j]=\max\left(f[i-1][j],\ f[i-1][j-c[i]]+w[i]\right)
$$
只考虑第 $i$ 件物品的策略放或不放 $\Rightarrow$ 只牵扯前 $i-1$ 件物品的问题：
- 不放第 $i$ 件物品：问题转化为“前 $i-1$ 件物品放入容量为 $j$ 的背包中”，价值为 $f[i-1][j]$
- 放第 $i$ 件物品：问题转化为“前 $i-1$ 件物品放入剩下的容量为 $j - c[i]$ 的背包中”，此时能获得的最大价值就是 $f[i-1][j-c[i]]$，再加上通过放入第 $i$ 件物品获得的价值 $w[i]$。
基本方法：
- 作一个 $N\times \left(C + 1\right)$ 的数组 $dp$ 考虑容积为 0 情况。$dp$ 表示在前 $i$ 个物品中，使用了 $j$ 个容积达到的最大价值。总之问题求啥 $dp$ 是啥。
- 根据实际情况，也常有 $(N + 1)\times (C+1)$
int[][] dp = new int[N + 1][C + 1];- $C$ 可以根据约束条件个数，拓展为多维度
int[] dp = new int[C + 1];- 设置边界条件：
- 初始化一定要和 $dp$ 数组的定义吻合
常见：
- $i = 0$ 表示不放进任何物品时，对于 $0\le j \le C$，$dp[i][j] = 0$
- $i = 0$ 表示放进第一个物品时，那么 $j < c[i],\ dp[0][j] = 0$；$j \ge c[i],\ dp[0][j] = w[0]$
- $j = 0$ 时，即背包容量为 $0$ 的话，即 $dp[i][0] = 0$
- 撰写状态转移方程
- 若 $j < c[i]$ 时，则不选第 $i$ 件物品，
p[i][j] = dp[i - 1][j]; - 若 $j \ge c[i]$ 时，则进行选择，
p[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
for(int i = 1; i < N; ++i) // 注意偏移值
for(int j = 0; j < C; ++j){
if(j < C[i - 1])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i - 1]] + w[i]);
}返回答案
dp[N][C]空间复杂度优化：上述方法无法再时间复杂度进行优化，但可以在空间复杂度进一步优化
对于 01 背包问题，因为只需要求最后一行最后一列值，即在「填表格」的时候，当前行总是参考了它上面一行 「头顶上」 那个位置和「左上角」某个位置的值。因此，我们可以只开一个一维数组，从后向前依次填表即可。
for (int i = 0; i < N; ++i)
for (int j = C; j >= c[i]; --j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);- 时间复杂度优化：还可以对上述循环在常数级进行优化
因为只需要知道 $dp[C]$ 的值，所以只要知道 $dp[c-w[N]]$ 即可。以此类推，对以第 $j$ 个背包，其实只需要知道到 $dp[C-sum\left(w[j],\cdots,w[N]\right)]$即可
for (int i = 0; i < N; ++i){
int bound=Math.max(V-sum(w[i..n]), c[i])
for (int j = C; j >= bound; --j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
}时间复杂度：$O\left(NC\right)$
空间复杂度（未优化）：$O\left(NC\right)$
空间复杂度（已优化）：$O\left(C\right)$
完全背包问题
题目描述：有 $N$ 种物品和一个容量为 $C$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的体积是 $c[i]$，价值是 $w[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
特点：每种物品有无限件
子问题定义状态：$dp[i][j]$ 表示选择前 $i$ 件物品时，容量为 $j$ 的背包可以获得最大价值
状态转移方程：$dp[i][j]=\max\left(dp[i-1][v-k\times c[i]]+k*w[i]\right)$
- 其中 $k$ 为第 $i$ 个物品的数量，因此 $0\le k\times c[i] \le j$
基本方法：
- 作一个 $N\times \left(C + 1\right)$ 的数组 $dp$ 考虑容积为 0 情况。$dp$ 表示在前 $i$ 个物品中任取，使用了 $j$ 个容积达到的最大价值。
int[][] dp = new int[N + 1][C + 1];设置边界条件
撰写状态转移方程
- 若 $j < c[i]$ 时，则不选第 $i$ 件物品，
p[i][j] = dp[i - 1][j]; - 若 $j \ge c[i]$ 时
- 不取物品 $i$：
dp[i][j] = dp[i - 1][j]; - 任取物品 $i$：
dp[i][j] = dp[i][j - c[i]] + w[i];
这里是和 01 背包主要区别
- 不取物品 $i$：
for(int i = 1; i < N; ++i) // 注意偏移值
for(int j = 0; j < C; ++j){
if(j < C[i - 1])
dp[i][j] = dp[i - 1][j];
else // 注意这里跟01背包只有下面一个下标不同，那就是“放i”这个选择
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - c[i - 1]] + w[i]); // 因为是可以重复放的，所以是dp[i]
}返回答案
dp[N][C]两种简单的优化方法
若物品 $i$，$j$ 满足 $c[i]\le c[j]$ 且 $w[i]\ge w[j]$，则去除物品 $j$显然物美价廉更受欢迎
- 该优化可以以 $O\left(N^2\right)$ 实现
- 该方法对于随机生成的数据，可以极大筛除物品件数
- 但是不会降低复杂度，最坏情况一件也不会剔除
去除所有体积大于 $C$ 的物品，然后使用计数排序单价最高的物品
- 该优化可以以 $O\left(C + N\right)$ 实现
- 优化为 $O\left(C\times N\right)$ 的算法
可以考虑将其转化为熟知的 01 背包问题的思路：将一种物品拆成多件物品进行计算
for (int i = 0; i < N; ++i)
for (int j = c[i]; j <= C; ++j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);与 01 背包问题只有循环次序不同：
- 01背包问题之所以逆序，是因为要确保每个物品只选择一次，在考虑第 $i$ 件物品时依据绝无已经选入第 $i$ 件的子结果
- 完全背包问题则需要考虑“加选一件第 $i$ 种物品”，正需要可能选入第 $i$ 件物品的子结果
时间复杂度（未优化）：$O\left(C\times\sum\dfrac C{c[i]}\right)$
空间复杂度（未优化）：$O\left(CN\right)$
时间复杂度（已优化）：$O\left(C\times N\right)$
空间复杂度（已优化）：$O\left(C\right)$
多重背包问题
题目描述：有 $N$ 种物品和一个容量为 $C$的背包。第 $i$ 种物品最多有 $n[i]$ 件可用，每件体积是 $c[i]$，价值是 $w[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
特点：物品有限件，其实把 $n$ 件物品摊开，那就是 01 背包问题
子问题定义状态：$dp[i][j]$ 表示选择前 $i$ 件物品时，容量为 $j$ 的背包可以获得最大价值
状态转移方程：$dp[i][j]=\max\left(dp[i-1][j-k\times c[i]]+k\times w[i]\right)$
- 其中 $k$ 为第 $i$ 个物品的数量，因此 $0\le k \le n[i]$
基本方法：
作一个 $N\times \left(C + 1\right)$ 的数组 $dp$
设置边界条件
撰写状态转移方程
- 若 $j < c[i]$ 时，则不选第 $i$ 件物品，
p[i][j] = dp[i - 1][j]; - 若 $j \ge c[i]$ 时
- 不取物品 $i$：
dp[i][j] = dp[i - 1][j]; - 任取物品 $i$：
dp[i][j] = dp[i - 1][j - k * c[i]] + k * w[i];
- 不取物品 $i$：
for(int i = 1; i < N; ++i) // 注意偏移值
for(int j = 0; j < C; ++j)
for(int k = 1; k <= n[i] && k * c[i] <=j; ++k)
dp[j] = Math.max(dp[j], dp[j - c[i] * k] + w[i] * k);- 返回答案
dp[N][C]
转换为 01 背包问题求解：
将第 $i$ 件物品转换为 $n[i]$ 件 01 背包中的物件，则得到物件个数为 $\sum n[i]$ 的 01 背包问题。该方法时间复杂度亦为 $O\left(C\times\sum{n[i]}\right)$。
- 小优化：01 + 完全背包
若 $c[i] \times n[i] \ge C$，则表明该物品拿不完背包就塞不下了，所以其数量上限没有必要，因此可以转换为完全背包。转换为 01 背包需要枚举，而完全背包可以省略枚举步骤，节省一定程度的时间复杂度。
for(int i = 1; i <= N; ++i){
if(n[i] * c[i] >= C){ // 转化为完全背包
for(int j = c[i]; j <= C; ++j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
}
else{ // 转化为 01 背包
for(int j = C; j >= c[i]; --j)
for(int k = n[i]; k >= 0; --k)
if(j >= k * c[i])
dp[j] = Math.max(dp[j], dp[j - k * c[i]] + k * w[i]);
}
}二进制表示
所谓二进制表示，即非将 $n$ 均分，而是利用二进制的指数上涨进行表示，具体说来就是将 $n[i]$ 划分为 $1,\ 2,\ 4,\ ,8,\ \cdots$
- 将数据转换为二进制
将数据拆为 $O\left(\log n[i]\right)$ 个元素
int cnt = 0; // 记录新的物体数
for(int i = 0; i < N; ++i){
int k = 1;
while(k <= n[i]){ // 实现1 2 4 8件原物品 合成为新物品
++cnt;
new_c[cnt] = k * c[i];
new_w[cnt] = k * w[i];
n[i] -= k;
k *= 2;
}
if(n[i]){ // 还有余数
++cnt;
new_c[cnt] = k * c[i];
new_w[cnt] = k * w[i];
}
}- 计算 01 背包
for(int i = 1; i <= cnt; ++i) // 01 背包
for(int j = C; j >= new_c[i]; --j)
dp[j] = Math.max(dp[j], dp[j - new_c[i]] + new_w[i]);单调队列优化
之前的思想中，我们均是对拿多少件物品进行分类。而根据要求拿物品之后，剩余体积一定小于每种物品体积。所以根据剩余物品进行分类——假设第 $i$ 种物品体积为 $c$，价值为 $w$，剩余体积一定为 $0,1,2,\cdots,c-1$。这个难度洗漱已经超出 NOIP 要求。
状态转移方程：
$dp[j] = \max\left(dp[j], dp[j - c] + w, dp[j - 2c] + 2w, \cdots, dp[j - (n-1)\times c] + (n-1)\times w, dp[j - n\times c] + n\times w\right)$
$dp[j+c] = \max\left(dp[j+c], dp[j] + w, dp[j - c] + 2w, \cdots, dp[j - (n-2)\times c] + (n-1)\times w, dp[j - (n-1)\times c] + n\times w\right)$
即 $dp[j]$ 和 $dp[j + c]$ 都是从 $n[i] + 1$ 中选择最大值，计算 $dp[j + c]$ 只是滑动窗口右移一步。使用单调队列可以在 $O(N)$ 复杂度下寻找最大值。
//多重背包问题： 限制每种物品可取次数
//究极优化：单调队列
const int M = 20010, N = 1010;
int n, m;
int dp[M], g[M];
int que[M]; //队列只存储在同余的集合中是第几个，不存储对应值
int main() {
cin >> n >> m;
for(int i = 0; i < n; i ++){
int v, w, s; // 体积，价值，个数
cin >> v >> w >> s;
memcpy(g, dp, sizeof dp); //复制一份副本g，因为这里会是从小到大，不能像0-1背包那样从大到小，所以必须申请副本存i-1状态的，不然会被影响
for(int r = 0; r < v; r ++) { //因为只有与v同余的状态 相互之间才会影响，余0,1,...,v-1 分为v组
int head = 0, tail = -1;
for(int k = 0; r + k * v <= m; k ++) { //每一组都进行处理，就相当于对所有状态都处理了
if(head <= tail && k - que[head] > s) head++; //队头不在窗口里面就踢出（队头距离要更新的dp超过了最大个数s，尽管它再大也要舍去，因为达不到）
//这第k个准备进来，把不大于它的队尾统统踢掉，也是为了保持队列的单调降（判断式实际上是两边同时减去了k * w）
//实际意义应该是 g[r + k * v] >= g[r + que[tail] * v] + (k - que[tail]) * w 为判断条件
while(head <= tail && g[r + k * v] - k * w >= g[r + que[tail] * v] - que[tail] * w) tail --;
que[++ tail] = k; //将第k个入列，队列只存储在同余中是第几个，不存储对应值
//余r的这组的第k个取队头更新，队头永远是使之max的决策
dp[r + k * v] = g[r + que[head] * v] + (k - que[head]) * w;
}
}
}
cout << dp[m] << endl;
return 0;
}时间复杂度（未优化）：$O\left(C\times\sum{n[i]}\right)$
空间复杂度（未优化）：$O\left(CN\right)$
时间复杂度（转换为 01 背包）：$O\left(C\times\sum{n[i]}\right)$
空间复杂度（转换为 01 背包）：$O\left(C\times\sum{n[i]}\right)$
时间复杂度（二进制表示优化）：$O\left(C\times\sum{\log n[i]}\right)$
空间复杂度（二进制表示优化）：$O\left(C\times\sum{\log n[i]}\right)$
时间复杂度（单调队列优化）：$O\left(C\times N\right)$
混合背包问题
特点：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）
for (int i = 1; i <= N; ++i){
//cin >> c >> w >> p;
if(n[i] == 0) //完全背包
for(int j = c[i]; j <= C; ++j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
else if(n[i] == -1) // 01背包
for(int j = C; j >= c[i]; --j)
dp[j] = Math.max(dp[j], dp[j - c[i]] + w[i]);
else{ //多重背包二进制优化
int num = Math.min(n[i], C / c[i]);
for(int k = 1; num > 0; k <<= 1){
if(k > num) k = num;
num -= k;
for (int j = C; j >= c[i] * k; --j)
dp[j] = Math.max(dp[j], dp[j - c[i] * k] + w[i] * k);
}
}
}
分组的背包问题
题目描述：有 $N$ 件物品和一个容量为 $C$ 的背包。第 $i$ 件物品的体积是 $c[i]$，价值是 $w[i]$。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
子问题定义状态：$dp[k][j]$ 表示选择前 $k$ 组物品时，容量为 $j$ 的背包可以获得最大价值
状态转移方程：$dp[k][j]=\max\left(dp[k-1][j], dp[k-1][j-c[i]]+w[i]\right)$，物品 $i\in$组 $k$
基本方法：
for (int i = 1; i <= n; i++){ // 对每个组迭代
// s[i]：第 i 组物品数量
for (int j = C; j >= 0; --j)
for (int k = 1; k <= s[i]; k++)
if (j >= c[k])
f[j] = Math.max(dp[j], dp[j - c[k]] + w[k]); // 由于每组物品只能选一个，所以可以覆盖之前组内物品最优解的来取最大值
}
