算法中的背包问题详解：部分背包与0-1背包

1. 背包问题概述

背包问题是组合优化中的经典问题，其核心目标是：在给定容量的背包中装入一组物品，使得物品的总价值最大化。根据物品是否可分割或重复选择，背包问题分为多个变种，其中最常见的两种是：

• 部分背包问题（Fractional Knapsack）

• 0-1背包问题（0-1 Knapsack）

其他变种包括完全背包、多重背包、分组背包等，本文重点讨论前两者。

2. 部分背包问题（Fractional Knapsack）

2.1 定义与特点

• 问题描述：给定一个容量为 WW 的背包和 nn 件物品，每件物品有重量 wiwi​ 和价值 vivi​。允许选择物品的任意比例（例如取物品的50%），求背包能容纳的最大总价值。

• 关键特点：

  • 物品可分割（如液体、粉末）。

  • 贪心算法可获得最优解。

2.2 贪心算法解决策略

由于物品可分割，最优策略是优先选择单位重量价值最高的物品。步骤如下：

1. 计算每件物品的价值密度：viwiwi​vi​​。

2. 按价值密度降序排列所有物品。

3. 依次装入物品，若当前物品可完整放入，则全取；否则取部分填满背包。

伪代码示例：

Sort items by v_i/w_i in descending order
total_value = 0
remaining_capacity = Wfor each item in sorted list:if remaining_capacity >= item.weight:total_value += item.valueremaining_capacity -= item.weightelse:fraction = remaining_capacity / item.weighttotal_value += fraction * item.valuebreak
return total_value

2.3 实例分析

示例：背包容量 W=50W=50，物品如下：

物品	重量	价值
A	10	60
B	20	100
C	30	120

1. 计算价值密度：

   • A: 66, B: 55, C: 44

2. 按降序排列：A → B → C

3. 装入过程：

   • 装入A（10→剩余40，价值+60）

   • 装入B（20→剩余20，价值+100）

   • 剩余容量20，装入C的 20303020​，价值+80

   • 总价值：60+100+80=24060+100+80=240

2.4 复杂度分析

• 时间复杂度：O(nlog⁡n)O(nlogn)（排序占主导）。

• 空间复杂度：O(1)O(1)（原地排序）。

2.5 应用场景

• 资源切割（如木材、金属）。

• 时间分配（如任务调度中选择收益最高的部分任务）。

• 物流运输中装载可分割货物。

---

3. 0-1背包问题（0-1 Knapsack）

3.1 定义与特点

• 问题描述：给定容量为 WW 的背包和 nn 件物品，每件物品只能选择放入（1）或不放入（0），求最大总价值。

• 关键特点：

  • 物品不可分割。

  • 动态规划是经典解法，贪心算法无法保证最优。

3.2 动态规划解决策略

动态规划通过构建二维表记录子问题的最优解，核心思想是状态转移。

状态定义

设 dp[i][j]dp[i][j] 表示前 ii 件物品在容量 jj 下的最大价值。

状态转移方程

dp[i][j]={dp[i−1][j]if wi>jmax⁡(dp[i−1][j],dp[i−1][j−wi]+vi)otherwisedp[i][j]={dp[i−1][j]max(dp[i−1][j],dp[i−1][j−wi​]+vi​)​if wi​>jotherwise​

伪代码示例：

Initialize dp[n+1][W+1] with zerosfor i from 1 to n:for j from 1 to W:if w[i-1] > j:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
return dp[n][W]

3.3 空间优化技巧

二维数组可优化为一维数组，通过逆序更新避免覆盖旧值：

dp = [0] * (W + 1)
for i in range(n):for j in range(W, w[i]-1, -1):dp[j] = max(dp[j], dp[j - w[i]] + v[i])
return dp[W]

3.4 实例分析

示例：背包容量 W=4W=4，物品如下：

物品	重量	价值
1	1	15
2	3	20
3	4	30

动态规划表（简化版）：

容量	0	1	2	3	4
物品0	0	15	15	15	15
物品1	0	15	15	20	35
物品2	0	15	15	20	35

最优解：物品1（15） + 物品2（20） = 35。

3.5 复杂度分析

• 时间复杂度：O(nW)O(nW)（伪多项式时间，与输入规模相关）。

• 空间复杂度：O(W)O(W)（优化后）。

3.6 应用场景

• 货物装载（如卡车运输不可拆分的货物）。

• 投资决策（选择互斥项目）。

• 密码学中的子集和问题。

4. 部分背包与0-1背包的对比

特征	部分背包	0-1背包
物品是否可分割	是	否
最优解算法	贪心算法	动态规划
时间复杂度	O(nlog⁡n)O(nlogn)	O(nW)O(nW)
适用场景	可分割资源	不可分割物品
是否总能得到最优解	是	是

5. 扩展：其他背包问题变种

1. 完全背包：每件物品可无限次选择。

2. 多重背包：每件物品有数量限制。

3. 多维背包：背包有多个容量约束（如重量和体积）。

4. 分组背包：物品分组，每组只能选一件。

6. 总结

部分背包问题和0-1背包问题在算法设计中具有重要地位。前者通过贪心算法高效解决，后者依赖动态规划处理更复杂的约束。理解它们的区别与联系，有助于在实际问题中选择合适的策略。未来可进一步探索其他变种问题，以适应更广泛的应用场景。