#include <bits/stdc++.h>
const int N = 110;
int n, V, f[N];
int main() {
std::cin >> n >> V;
for (int i = 1, v, w, s; i <= n; ++i) {
std::cin >> v >> w >> s;
for (int j = V; ~j; --j) // 一定要把 j 放在外面！使用上一层的，倒序遍历
for (int k = 0; k <= s && k * v <= j; ++k)
f[j] = std::max(f[j], f[j - k * v] + k * w);
}
std::cout << f[V] << std::endl;
return 0;
}
#include <bits/stdc++.h>
const int N = 2e3 + 10;
int n, V, f[N];
int main() {
std::cin >> n >> V;
for (int i = 1, v, w, s; i <= n; ++i) {
std::cin >> v >> w >> s;
for (int k = 1; k <= s; k <<= 1) {
for (int j = V; j >= k * v; --j) // 使用上一层的，倒序遍历
f[j] = std::max(f[j], f[j - k * v] + k * w);
s -= k;
}
if (s)
for (int j = V; j >= s * v; --j)
f[j] = std::max(f[j], f[j - s * v] + s * w);
}
std::cout << f[V] << std::endl;
return 0;
}
#include <iostream>
const int N = 1e2 + 10;
int n, V, M, f[N][N];
int main() {
std::cin >> n >> V >> M;
for (int i = 1, v, m, w; i <= n; ++i) {
std::cin >> v >> m >> w;
for (int j = V; j >= v; --j)
for (int k = M; k >= m; --k)
f[j][k] = std::max(f[j][k], f[j - v][k - m] + w);
}
std::cout << f[V][M] << std::endl;
return 0;
}
有依赖的背包问题
题目描述
有 n 个物品和一个体积为 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
第 i 个物品体积为 v_i，价值为 w_i，依赖的父结点编号为 p_i。若 p_i=-1，则表示根节点。
求解将哪些物品装入背包，可使物品总体积不超过背包体积，且总价值最大。
输出最大价值。
状态表示
集合
令 f_{u,j} 表示 在以 u 为根结点的子树中（包含 u），总体积不超过 j 的方案集合。
属性
集合中的 最大价值。
状态转移
对于每个儿子，可以用体积划分集合。
由于每个儿子只能有一种体积，所以相当于一个分组背包。
初始条件
f_{u,j}=0\,(j\in[1,n],j\in[1,V])
最终结果
最终结果应为在根结点的子树中，总体积不超过 V 的方案集合，即
f_{\text{root},V}
## 代码实现
```cpp
#include <bits/stdc++.h>
const int N = 110;
std::vector<int> g[N];
int n, V, root, v[N], w[N], f[N][N];
void dp(int u) {
for (auto son : g[u]) { // 遍历儿子
dp(son);
for (int j = V - v[u]; ~j; --j) // 由于一定要包含 u 结点，所以最大体积为 V-v[u]
for (int k = 0; k <= j; ++k)
f[u][j] = std::max(f[u][j], f[u][j - k] + f[son][k]);
}
for (int i = V; i >= v[u]; --i) f[u][i] = f[u][i - v[u]] + w[u]; // 加入 u，更新
for (int i = 0; i < v[u]; ++i) f[u][i] = 0; // 不可能的情况
}
int main() {
std::cin >> n >> V;
for (int i = 1, p; i <= n; ++i) {
std::cin >> v[i] >> w[i] >> p;
if (p == -1) root = i;
else g[p].push_back(i);
}
dp(root);
std::cout << f[root][V] << std::endl;
return 0;
}
```
# 背包问题求方案数
## 题目描述
有 $n$ 件物品，体积为 $V$ 的背包。
第 $i$ 件物品体积为 $v_i$，价值为 $w_i$，每件物品只能用一次。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。
输出 **最优选法的方案数**。注意答案可能很大，请输出答案模 $10^9+7$ 的结果。
## 状态表示
### 集合
令 $f_{i,j}$ 表示从前 $i$ 个物品中选，总体积 **恰好** 为 $j$ 的方案集合。
### 属性
集合中的 **最大价值**。
## 状态转移
令 $g_{i,j}$ 表示到达 $f_{i,j}$ 的方案数。
可以知道，
$$
f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}
$$
可以分三类讨论：
- $f_{i-1,j}>f_{i-1,j-v_i}+w_i$：此时 $f_{i,j}\gets f_{i-1,j}$。那么 $g_{i,j}\gets g_{i-1,j}$。
- $f_{i-1,j} < f_{i-1,j-v_i}+w_i$：此时 $f_{i,j}\gets f_{i-1,j-v_i}+w_i$。那么 $g_{i,j}\gets g_{i-1,j-v}$。
- $f_{i-1,j} = f_{i-1,j-v_i}+w_i$：此时两种前置情况都可以到达 $f_i,j$。那么 $g_{i,j}\gets g_{i-1,j}+g_{i-1,j-v}$。
## 初始条件
由于 $f_{i,j}$ 表示 **恰好** 总体积为 $j$ 的方案集合，那么
$$
\begin{cases}
f_{0,0}=0,g_{0,0}=1&\\
f_{0,j}=-\infty,g_{0,j}=0&(j\in[1,V])
\end{cases}
$$
## 最终结果
令 $k$ 表示背包中的最大总价值，即 $f$ 中的最大值。此时答案为：
$$
\sum_{\mathclap{\substack{i,j \ i + j = f_{i,j}}}} (i + j)
$$
## 代码实现
```cpp
#include <bits/stdc++.h>
const int N = 1e3 + 10;
const int MOD = 1e9 + 7;
int n, V, ans, cnt, f[N], g[N];
int main() {
std::cin >> n >> V;
memset(f, -0x3f, sizeof(f));
f[0] = 0, g[0] = 1;
for (int i = 1, v, w; i <= n; ++i) {
std::cin >> v >> w;
for (int j = V; j >= v; --j) {
int mx = std::max(f[j], f[j - v] + w), s = 0;
if (mx == f[j]) s = g[j];
if (mx == f[j - v] + w) (s += g[j - v]) %= MOD;
f[j] = mx, g[j] = s;
}
}
ans = *std::max_element(f, f + V + 1);
for (int i = 0; i <= V; ++i)
if (f[i] == ans) cnt += g[i];
std::cout << cnt << std::endl;
return 0;
}
```
# 背包问题求具体方案
## 题目描述
有 $n$ 件物品和一个体积为 $V$ 的背包。
第 $i$ 件物品体积为 $v_i$，价值为 $w_i$，每件物品只能用一次。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包体积，且总价值最大。
输出 **字典序最小的方案**。这里的字典序是指：所选物品的编号所构成的序列。
## 状态表示
### 集合
令 $f_{i,j}$ 表示从**后** $n-i+1$ 件物品中选，总体积不超过 $j$ 的方案集合（至于为什么要这样，见下文）。
### 属性
集合中的最大价值。
## 状态转移
容易知道，
$$
f_{i,j}\gets \max\{f_{i+1,j},f_{i+1,j-v_i}+w_i\}
$$
## 初始条件
$$
f_{n+1,j}=0\,(j\in[0,V])
$$
## 获得方案
题目要求输出 **字典序最小的方案**。从前往后考虑，每个物品必然是 **能选就选**。
如何知道第 $i$ 个物品能不能选呢？
可以看 $f_{i,j}$ 是否从**选第 $i$ 个物品**的情况转移过来（如果 $f_{i+1,j}=f_{i+1,j-v_i}+w_i$，根据能选就选的原则，也得选）
> Q：为什么要这样定义 $f_{i,j}$？
>
> A：倒着定义，$f_{1,V}$ 就是**全局最优解**。根据转移的情况来向后推，$f_{2,\Delta V},f_{2,\Delta V'},\cdots$ 都是全局最优解，保证输出结果是全局最优方案。但是如果正着定义，$f_{1,V}$ 是**局部最优解**，在后面的转移中可能没有入选，会导致输出结果不是全局最优方案。
>
> ### 提供一组数据：
>
> #### 输入
>
> ```
> 4 5
> 1 2
> 2 4
> 3 4
> 4 6
> ```
>
> #### 输出一（倒着定义）
>
> ```
> 1 4
> ```
>
> #### 输出二（正着定义）
>
> ```
> 1 2
> ```
> 可以发现输出二 只是纯粹的能选就选，没有考虑全局情况。
>
> （这里可能解释不清楚，轻喷/kk）
详见代码。
## 代码实现
```cpp
#include <bits/stdc++.h>
const int N = 1e3 + 10; // 假设 n,V 同阶
int n, V, v[N], w[N], f[N][N]; // 此时不能压成一维了
int main() {
std::cin >> n >> V;
for (int i = 1; i <= n; ++i) std::cin >> v[i] >> w[i];
for (int i = n; i; --i)
for (int j = 0; j <= V; ++j) {
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = std::max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
int j = V; // 剩余空间的体积
for (int i = 1; i <= n; ++i) {
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) { // 从选第 i 个的情况转移过来
std::cout << i << " ";
j -= v[i];
}
}
std::cout << std::endl;
return 0;
}
```