---
tags: [算法分析与设计]
abstract: 分治、动态规划与贪心的关系
finished: false
返回目录: [[计算机系/算法分析与设计/算法分析|算法分析与设计学习指南]]
相关主题: [[计算机系/算法分析与设计/算法分析2动态规划|动态规划]]、[[计算机系/算法分析与设计/算法分析3贪心|贪心算法]]
---
上一篇: [[计算机系/算法分析与设计/算法分析2动态规划|上一篇]]
下一篇: [[计算机系/算法分析与设计/算法分析3贪心|下一篇]]
前置知识: [[计算机系/算法分析与设计/算法分析2动态规划|前置知识]]


# 分治、动态规划与贪心：综合示例
W = 5
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
max_value, selected_items = knapsack_01(W, weights, values)
print("最大价值:", max_value)          # 输出: 37
print("所选物品编号:", selected_items) # 输出: [3, 1, 0]（对应物品 4、2、1）


### **举个具体例子**

假设：

- 背包容量 W=4 W=4。
    
- 物品列表：
    
    - 物品 0：重量=1，价值=15
        
    - 物品 1：重量=2，价值=20
        
    - 物品 2：重量=3，价值=30
        

计算 `dp[3][4]`（前 3 件物品，背包容量 4 时的最大价值）：

1. **考虑物品 2（重量=3，价值=30）**：
    
    - **不放**：`dp[2][4]`（前 2 件物品在容量 4 时的最大价值，假设是 35）。
        
    - **放**：  
        背包剩余容量 4−3=14−3=1，所以价值 = `dp[2][1] + 30`（前 2 件物品在容量 1 时的最大价值 + 30）。
        
    - 比较两种情况，取更大的值。
        


### **情况 1：`i` 从 1 开始（更常见）**

- **物品编号**：`i=1` 表示第 1 个物品，`i=2` 表示第 2 个物品，……，`i=n` 表示第 n 个物品。
    
- **DP 表定义**：
    
    - `dp[i][w]`：**前 `i` 件物品**（物品 1~ 物品 i）在容量 `w` 时的最大价值。
        
    - **初始化**：`dp[0][w] = 0`（前 0 件物品，价值为 0）。
        
- **状态转移方程**：
    
    dp[i][w]={dp[i−1][w]if w<weight[i−1]max⁡(dp[i−1][w], dp[i−1][w−weight[i−1]]+value[i−1])if w≥weight[i−1]dp[i][w]={dp[i−1][w]max(dp[i−1][w], dp[i−1][w−weight[i−1]]+value[i−1])​if w<weight[i−1]if w≥weight[i−1]​
    - **注意**：`weight[i-1]` 和 `value[i-1]` 是因为物品的数组索引从 `0` 开始（代码中通常用 `0-based` 数组存储物品）。
        

#### **例子**

- 物品列表：`weights = [2, 1, 3], values = [12, 10, 20]`（代码中索引为 0、1、2）。
    
- `dp[1][3]` 表示“前 1 件物品（即物品 0）在容量 3 时的最大价值”，此时：
    
    - `weight[0] = 2`, `value[0] = 12`。
        
    - 因为 `3 ≥ 2`，所以 `dp[1][3] = max(dp[0][3], dp[0][1] + 12) = max(0, 0 + 12) = 12`。
        


### **为什么通常从 `i=1` 开始？**

1. **更直观**：`dp[i][w]` 表示“前 `i` 件物品”，与自然语言描述一致。
    
2. **避免边界问题**：`i=0` 可以统一表示“没有物品”，无需处理负索引。
    
3. **代码一致性**：大多数教材和实现采用 `i=1` 的写法。
    


### **代码对比**

#### 写法 1（`i` 从 1 开始）：

python

def knapsack(W, weight, value):
    n = len(weight)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):  # i 从 1 到 n
        for w in range(W + 1):
            if w < weight[i-1]:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])
    return dp[n][W]

#### 写法 2（`i` 从 0 开始）：

python

def knapsack(W, weight, value):
    n = len(weight)
    dp = [[0] * (W + 1) for _ in range(n)]
    for i in range(n):  # i 从 0 到 n-1
        for w in range(W + 1):
            if i == 0:
                if w >= weight[i]:
                    dp[i][w] = value[i]
            else:
                if w < weight[i]:
                    dp[i][w] = dp[i-1][w]
                else:
                    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
    return dp[n-1][W]


### **情况 1：`i` 从 0 开始（直接对应物品索引）**

- **定义**：`dp[i][w]` 表示 **考虑物品 0 到物品 i**（前 i+1 个物品），背包容量为 `w` 时的最大价值。
    
- **初始化**：
    
    - `dp[-1][w] = 0`（没有物品时价值为 0，代码中需要特殊处理）。
        
- **状态转移**：
    
    - 如果不选物品 i：`dp[i][w] = dp[i-1][w]`
        
    - 如果选物品 i（且能装下）：`dp[i][w] = dp[i-1][w - weight[i]] + value[i]`
        
- **例子**：
    
    - `dp[0][w]`：只考虑物品 0（重量 1，价值 15）。
        
    - `dp[1][w]`：考虑物品 0 和物品 1。
        
    - `dp[2][w]`：考虑物品 0、1、2。
        

#### **代码实现（i 从 0 开始）**

python

def knapsack(W, weight, value):
    n = len(weight)
    dp = [[0] * (W + 1) for _ in range(n)]  # dp[n][W+1]
    
    for i in range(n):  # i 从 0 到 n-1
        for w in range(W + 1):
            if i == 0:  # 只有物品 0
                if w >= weight[i]:
                    dp[i][w] = value[i]
            else:
                if w < weight[i]:
                    dp[i][w] = dp[i-1][w]
                else:
                    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
    return dp[n-1][W]


### **你的例子中 `i` 应该从几开始？**

1. **如果你用 `i` 直接对应物品索引（0,1,2）**：
    
    - `i` 从 0 开始，`dp[i][w]` 表示考虑物品 0~ 物品 i。
        
    - 需要处理 `i=0` 的边界情况（如代码 1 所示）。
        
2. **如果你用 `i` 表示“前 i 个物品”**：
    
    - `i` 从 1 开始，`dp[i][w]` 表示前 i 个物品（物品 0~ 物品 i-1）。
        
    - 更直观，代码更简洁（如代码 2 所示）。
        

**推荐使用 `i` 从 1 开始的写法**（情况 2），因为：

- 无需处理 `i=0` 的边界，逻辑更清晰。
    
- 与大多数教材和算法描述一致。
    


### **总结**

- **你的物品列表索引是 `0,1,2`，但 `i` 的起始值由 `dp[i][w]` 的定义决定**：
    
    - `i` 从 0 开始：`dp[i][w]` 对应物品 0~ 物品 i。
        
    - `i` 从 1 开始：`dp[i][w]` 对应前 i 个物品（物品 0~ 物品 i-1）。
        
- **推荐 `i` 从 1 开始**，代码更简洁，逻辑更清晰。