背包问题（Knapsack Problem）是经典的动态规划问题之一。它描述的是在容量有限的背包中，选择若干物品放入，使得总价值最大化。
01背包
01背包问题，就是给定 n 种物品，每种物品都有重量和价值，每种物品都只有一个。
求最大价值
题目链接：2. 01背包问题 – AcWing题库
题目描述：
\(n\) 件物品，背包容量为 \(m\)，每个物品都有一个体积 \(v\) 和价值 \(w\)，每件物品只有一个，求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
状态定义：
\(dp[j]\)表示容量为 \(j\) 时的最大价值。
状态转移：
\(dp[j] = max(dp[j], dp[j – v[i]] + w[i])\)
解决代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
for (int i = 0; i < n; ++i)
cin >> v[i] >> w[i];
vector<ll> dp(m + 1, 0);
for (int i = 0; i < n; ++i)
for (int j = m; j >= v[i]; --j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl;
}相关题目：
1.https://www.luogu.com.cn/problem/P1048
2.https://www.luogu.com.cn/problem/P1049
3.https://www.luogu.com.cn/problem/P1060
4.https://www.luogu.com.cn/problem/P8742
求方案数
题目链接：https://www.luogu.com.cn/problem/P1164
题目描述：
\(n\) 种菜品，拥有 \(m\) 元，第 \(i\) 种菜品价值 \(a_i\) 元，每个菜只有一份，把身上的钱全花完，有多少种点菜方法。
状态定义：
\(dp[j]\)表示金额为 \(j\) 时的购买方法。
初始化：
\(dp[0] = 1;\)
金额为 \(0\) 时，有 \(1\) 种选择方法。
状态转移：
\(dp[j] += dp[j – a[i]];\)
解决代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a)
cin >> x;
vector<int> dp(m + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = m; j >= a[i]; --j)
dp[j] += dp[j - a[i]];
cout << dp[m] << endl;
}相关题目：
求最优方案数
完全背包
01背包问题，就是给定 n 种物品，每种物品都有重量和价值，每种物品都有无限个。
求最大价值
题目链接：3. 完全背包问题 – AcWing题库
题目描述：
\(n\) 件物品，背包容量为 \(m\)，每个物品都有一个体积 \(v\) 和价值 \(w\)，每件物品有无限个，求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
状态定义：
\(dp[j]\)表示容量为 \(j\) 时的最大价值。
状态转移：
\(dp[j] = max(dp[j], dp[j – v[i]] + w[i])\)
解决代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
for (int i = 0; i < n; ++i)
cin >> v[i] >> w[i];
vector<ll> dp(m + 1, 0);
for (int i = 0; i < n; ++i)
for (int j = v[i]; j <= m; ++j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[m] << endl;
}相关题目：
1.https://www.luogu.com.cn/problem/P1616
2.https://www.luogu.com.cn/problem/P2842
求组合方案数（不考虑顺序）
题目链接：https://www.luogu.com.cn/problem/P2834
题目描述：
\(n\) 种面额的纸币，需要支付 \(m\) 的金额，第 \(i\) 种纸币面额为 \(a_i\) 并且有无限张，有多少种纸币组合恰好支付金额 \(w\)，答案对 \(10^9 + 7\) 取模。
状态定义：
\(dp[j]\)表示第 \(j\) 种金额有几种纸张方案数。
初始化：
\(dp[0] = 1;\)
金额为 \(0\) 时，有 \(1\) 种纸张选择方法。
状态转移：
\(dp[j] = (dp[j] + dp[j – a[i]]) \text{% MOD};\)
解决代码：
void solve()
{
ll n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a)
cin >> x;
const int inf = 1e9;
vector<ll> dp(m + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = a[i]; j <= m; ++j)
dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
cout << dp[m] << endl;
}相关题目：
求排列方案数（考虑顺序）
与组合方案数的区别：
- 组合型的外层是 币种，因为顺序不重要：一旦选择了某个币种，它的贡献就固定了，不会因为放前面还是放后面而产生新方案。
- 排列型的外层是 金额，因为顺序重要：需要确保每一个位置都能选择不同的币种，所以要枚举“最后一步用了哪张币”，这样才能把顺序区分开。
题目链接：https://www.luogu.com.cn/problem/P2840
题目描述：
\(n\) 种面额的纸币，需要支付 \(m\) 的金额，第 \(i\) 种纸币面额为 \(a_i\) 并且有无限张，有多少种纸币组合恰好支付金额 \(w\)，同样的纸币组合如果支付顺序不同，会被视作不同的方式，答案对 \(10^9 + 7\) 取模。
状态定义：
\(dp[j]\)表示第 \(j\) 种金额有几种纸张方案数。
初始化：
\(dp[0] = 1;\)
金额为 \(0\) 时，有 \(1\) 种纸张选择方法。
状态转移：
\(dp[j] = (dp[j] + dp[j – a[i]]) \text{% MOD};\)
解决代码：
void solve()
{
ll n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a)
cin >> x;
const int inf = 1e9;
vector<ll> dp(m + 1, 0);
dp[0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 0; j < n; ++j)
if (i >= a[j])
dp[i] = (dp[i] + dp[i - a[j]]) % MOD;
cout << dp[m] << endl;
}相关题目：
暂无。
