33DAI：批量导入三三文档

2026-05-20T18:24:09Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第65行：		第65行：
	[[Category:动态规划]]		[[Category:动态规划]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:27Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 背包问题 ==

背包问题是一类经典的 DP 问题：给定 <math>n</math> 个物品，每个物品有体积（重量）<math>w_i</math> 和价值 <math>v_i</math>，在总容量不超过 <math>W</math> 的前提下，求最大总价值。

== 01 背包 ==

每个物品只能选或不选（0 或 1 次）。

<syntaxhighlight lang="cpp">
int dp[MAXW]; // 一维优化，dp[j] = 容量 j 的最大价值
memset(dp, 0, sizeof dp);

for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--) // 倒序：防止同一物品被多次使用
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
</syntaxhighlight>

== 完全背包 ==

每个物品可选无限次。

<syntaxhighlight lang="cpp">
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= W; j++) // 正序：允许同一物品多次使用
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
</syntaxhighlight>

== 多重背包 ==

每个物品有 <math>k_i</math> 个。可用'''二进制拆分'''优化：

<syntaxhighlight lang="cpp">
// 将 k 个物品拆成 logs 组：1, 2, 4, ..., 剩余
for (int i = 1; i <= n; i++)
{
int k = cnt[i]; // 该物品的个数
for (int t = 1; t <= k; t <<= 1)
{
k -= t;
// 把 t 个物品视为一个"新物品"，做 01 背包
for (int j = W; j >= t * w[i]; j--)
dp[j] = max(dp[j], dp[j - t * w[i]] + t * v[i]);
}
if (k)
{
for (int j = W; j >= k * w[i]; j--)
dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
}
}
</syntaxhighlight>

== 分组背包 ==

物品分成若干组，每组最多选一个：

<syntaxhighlight lang="cpp">
for (int grp = 1; grp <= g; grp++)
for (int j = W; j >= 0; j--) // 倒序
for (int i : group[grp])
if (j >= w[i])
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
</syntaxhighlight>

[[Category:动态规划]]
[[Category:三三文档]]

12-动态规划/03-背包DP - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档