# 0-1背包问题深度讲解

## 一、算法本质解析

**核心思想**：在给定容量的背包中，从n个物品中选择若干物品装入，每个物品只能选或不选，使得总价值最大。

**适用场景与边界条件**：

-   适用于资源有限的最优选择问题
-   每个物品只能使用一次（0-1特性）
-   物品重量和价值均为正整数
-   背包容量为正整数

**时间/空间复杂度推导**：

-   时间复杂度：O(n×W)，n为物品数量，W为背包容量，需要填充n×W的状态表
-   空间复杂度：O(n×W)，使用二维DP表；可优化至O(W)，使用一维滚动数组

**状态转移方程**：

```bash
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
```

含义：对于第i个物品，在容量w下，选择"不装"或"装"中的较大值。

---

## 二、完整代码实现（Python）

```python
def knapsack_01(weights, values, capacity):
    """
    0-1背包问题标准解法
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 最大价值
    """
    n = len(weights)
    
    # 边界条件处理
    if n == 0 or capacity <= 0:
        return 0
    
    # 创建DP表，dp[i][w]表示前i个物品在容量w下的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # 填充DP表
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            # 选第i个物品（如果容量允许）
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - weights[i-1]] + values[i-1])
    
    return dp[n][capacity]


def knapsack_01_optimized(weights, values, capacity):
    """
    空间优化版本 - 使用一维数组
    """
    n = len(weights)
    if n == 0 or capacity <= 0:
        return 0
    
    # 一维DP数组，从后向前遍历避免重复使用物品
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 必须从后向前遍历，确保每个物品只使用一次
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]
```

---

## 三、执行过程可视化

**测试数据**：

```python
weights = [2, 3, 4, 5]      # 4个物品的重量
values = [3, 4, 5, 8]       # 对应价值
capacity = 8                # 背包容量
```

**DP表填充过程**（二维版本）：

| 物品\\容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0个物品 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 物品1(2,3) | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 物品2(3,4) | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 物品3(4,5) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
| 物品4(5,8) | 0 | 0 | 3 | 4 | 5 | 8 | 9 | 11 | 12 |

**最终输出**：最大价值 = 12

**最优选择方案**：物品1 + 物品4（重量2+5=7≤8，价值3+8=11）或 物品2 + 物品3 + 物品1（重量3+4+2=9>8，不可行）

实际最优：物品2 + 物品4（重量3+5=8，价值4+8=12）✓

---

## 四、常见变式与扩展

| 变式类型 | 核心差异 | 解决方案 |
| --- | --- | --- |
| 完全背包 | 物品可无限次使用 | 内层循环从前往后遍历 |
| 多重背包 | 物品有数量限制 | 拆分为多个0-1物品或二进制优化 |
| 恰好装满 | 必须装满背包 | 初始化dp\[0\]=0，其他为-∞ |
| 求方案数 | 统计所有可行方案 | dp\[w\] += dp\[w-weight\[i\]\] |
| 二维费用背包 | 两个约束条件 | 增加一维状态dp\[w1\]\[w2\] |

**实际工程应用场景**：

-   资源分配：服务器CPU/内存分配优化
-   投资组合：有限资金下的最优投资组合
-   货物装载：货车/集装箱装载优化
-   考试策略：有限时间下的选题得分最大化

---

## 五、易错点与调试技巧

| 易错点 | 正确做法 | 调试观察点 |
| --- | --- | --- |
| 物品索引偏移 | weights\[i-1\]对应第i个物品 | 打印i与i-1的对应关系 |
| 一维优化遍历方向 | 必须从后向前 | 检查dp数组是否被重复使用 |
| 容量边界 | w >= weights\[i\]才能装 | 添加容量判断日志 |
| 初始化错误 | dp全为0（不要求装满） | 验证dp\[0\]\[0\]=0 |
| 返回值错误 | 返回dp\[n\]\[capacity\] | 检查最终状态位置 |

**性能测试数据**：

```python
# 小规模测试
weights_small = [1, 2, 3]
values_small = [10, 20, 30]
capacity_small = 5
# 预期输出：50（选物品2和3）

# 大规模测试
import random
weights_large = [random.randint(1, 100) for _ in range(1000)]
values_large = [random.randint(1, 100) for _ in range(1000)]
capacity_large = 5000
# 用于测试算法性能和内存占用
```

**调试技巧**：

1.  打印DP表前3行和前5列，验证状态转移是否正确
2.  使用小规模数据手动计算验证
3.  对比二维版本和一维优化版本的结果一致性
4.  添加计时器测试不同规模下的运行时间

---

## 六、测试用例汇总

```python
# 测试用例1：基础案例
assert knapsack_01([2, 3, 4, 5], [3, 4, 5, 8], 8) == 12

# 测试用例2：容量不足
assert knapsack_01([5, 6, 7], [10, 20, 30], 3) == 0

# 测试用例3：单个物品
assert knapsack_01([5], [10], 5) == 10

# 测试用例4：空物品列表
assert knapsack_01([], [], 10) == 0

# 测试用例5：优化版本验证
assert knapsack_01_optimized([2, 3, 4, 5], [3, 4, 5, 8], 8) == 12

print("✅ 所有测试用例通过！")
```

背包问题深度讲解 一、算法本质解析 核心思想：在给定容量的背包中，从n个物品中选择若干物品装入，每个物品只能选或不选，使得总价值最大。 适用场景与边界条件： 适用于资源有限的最优选择问题 每个物品只能使用一次（0-1特性） 物品重量和价值均为正整数 背包容量为正整数 时间/空间复杂度推导： 时间复杂度：O(n×W)，n为物品数量，W为背包容量，需要填充n×W的状态表 空间复杂度：O(n×W)，使用

算法知识一一背包问题

算法

编程语言

背包问题0-1算法完整指南：解析动态规划核心思想、状态转移方程及Python实现，涵盖二维与一维空间优化、典型案例演示、5种变式解决方案及易错点调试技巧，附完整测试用例与性能优化建议。

性能测试

服务器

Python

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

算法知识一一背包问题-腾讯云开发者社区-腾讯云

算法知识一一背包问题

算法知识一一背包问题

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐