目录
背包问题是一种经典的优化问题，常见的形式有 0-1 背包问题和完全背包问题。这里将介绍 0-1 背包问题的动态规划求解方法。
问题描述
给定一组物品，每个物品都有一定的重量 \(w_i\) 和价值 \(v_i\)，目标是选择一些物品，使得它们的总重量不超过背包的最大承重 \(C\)，同时使得总价值最大化。
动态规划解法
1. 定义状态
定义 dp[i][j] 表示前 i 个物品放入容量为 j 的背包的最大价值。
2. 状态转移方程
-
如果不选择第
\[dp[i][j] = dp[i-1][j] \]i个物品： -
如果选择第
\[dp[i][j] = dp[i-1][j - weight[i-1]] + value[i-1] \]i个物品（前提是它的重量小于等于j）： -
综合考虑，状态转移方程为：
\[dp[i][j] = \begin{cases} dp[i-1][j] & \text{if } weight[i-1] > j \\ \max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1]) & \text{otherwise} \end{cases} \]
3. 初始化
dp[0][j] = 0，表示没有物品时，价值为 0。dp[i][0] = 0，表示背包容量为 0 时，价值也为 0。
4. 实现细节
通常我们只需要当前行和上一行的值，因此可以优化空间复杂度，使用一维数组代替二维数组。
Python 示例代码
以下是 0-1 背包问题的动态规划实现：
def knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 示例数据
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
max_value = knapsack(weights, values, capacity)
print("最大价值:", max_value)
复杂度分析
- 时间复杂度：O(n * capacity)，其中
n是物品数量。 - 空间复杂度：O(capacity)，因为我们使用了一维数组来存储结果。
结论
动态规划是一种有效的求解背包问题的方法，通过构建状态转移方程和优化存储，可以高效地计算出最大价值。
0-1 背包问题通常不能用贪心算法来求解，因为贪心算法并不总是能够找到最优解。贪心法适合于某些特定的背包问题，例如完全背包问题或分数背包问题（fractional knapsack problem），但对于 0-1 背包问题，贪心法可能会得到次优解。
贪心法求解
在 0-1 背包问题中，每个物品只能选择一次。贪心法的思路是选择当前最优的物品，然而这并不保证整体的最优解。下面是一个简要的说明以及示例，展示贪心法为何不适用于 0-1 背包问题。
贪心法的想法
贪心法通常会根据某种准则（如价值密度）选择物品。对于 0-1 背包问题，可以考虑以下步骤：
- 计算价值密度：计算每个物品的价值密度（价值/重量）。
- 按价值密度排序：将物品按价值密度从高到低排序。
- 选择物品：依次选择物品，直到背包满。
示例
假设有以下物品和背包容量：
- 物品1：重量 1，价值 1
- 物品2：重量 3，价值 4
- 物品3：重量 4，价值 5
- 物品4：重量 5，价值 7
背包容量为 7。
贪心选择过程
-
计算价值密度：
- 物品1：1/1 = 1
- 物品2：4/3 ≈ 1.33
- 物品3：5/4 = 1.25
- 物品4：7/5 = 1.4
-
按价值密度排序：
- 物品4（1.4）
- 物品2（1.33）
- 物品3（1.25）
- 物品1（1）
-
选择物品：
- 选择物品4（重量 5，价值 7），剩余容量 2。
- 选择物品2（重量 3，价值 4）不行，跳过。
- 选择物品3（重量 4，价值 5）不行，跳过。
- 选择物品1（重量 1，价值 1），剩余容量 1。
最终得到的总价值为 8（物品4 + 物品1），但最优解是物品2和物品3，总价值为 9。
结论
由于贪心算法只关注当前的局部最优选择，无法保证获得全局最优解，因此不适用于 0-1 背包问题。对于 0-1 背包问题，推荐使用动态规划方法，以确保能够找到最优解。
标签：背包,capacity,问题,物品,价值,dp,贪心 From： https://www.cnblogs.com/Mount256/p/18565868