GeekIt

背包可视化工具

动画演示 0/1 背包动态规划——逐格填充 DP 表,高亮依赖关系

物品(重量, 价值)· 背包容量 W = 10
物品1: w=2, v=3物品2: w=3, v=4物品3: w=4, v=6物品4: w=5, v=8
dp[i][w]012345678910
0 物品00000000000
1: w2 v3
2: w3 v4
3: w4 v6
4: w5 v8
初始化:0 个物品时,任意容量的价值都是 0
速度
0 / 45
当前单元格跳过依赖选取依赖最优值

伪代码

dp[0][w] = 0 // 0 个物品时价值为 0
for i = 1 到 n: // 逐个考虑物品
for w = 0 到 W: // 逐个容量
skip = dp[i-1][w] // 跳过物品 i
take = dp[i-1][w-wᵢ] + vᵢ // 选取(若放得下)
dp[i][w] = max(skip, take)
answer = dp[n][W]
时间复杂度 O(n·W) · 空间复杂度 O(n·W)

复杂度

时间
O(n·W)
空间
O(n·W)
空间(滚动优化)
O(W)
问题类别
NP难

O(n·W) 是伪多项式时间复杂度——W 较小时很快,但 W 的输入规模随位数指数增长。0/1 背包本身是 NP 难问题。

常见问题

为什么使用此工具

  • • 观看用动态规划而非暴力枚举解决 0/1 背包问题的全过程。
  • • 注意每个单元格依赖的两个来源:上方(跳过)与左上(选取)。
  • • 理解 O(n·W) 运行时间与指数级暴力搜索的鲜明对比。
  • • 完全在浏览器中运行。无需注册,无需上传文件。

使用方法

  1. 1 按「运行」按钮,逐个单元格填充动态规划表。
  2. 2 每一行代表一个物品;每一列代表一个容量,范围从 0 到 W。
  3. 3 单元格显示最佳选择:跳过该物品(蓝框依赖)或选取该物品(绿框依赖)。
  4. 4 右下角单元格的值就是最优价值。按「随机」更换物品组再看一遍。

关于背包可视化

在线背包(0/1 Knapsack)可视化工具,动画演示动态规划表格的逐格填充过程。高亮显示每个单元格的两个依赖(跳过/选取),支持运行/单步控制、速度调节、随机物品组,最优值实时显示。完全在浏览器中运行,无需注册,注重隐私。直观展示 O(n·W) 伪多项式复杂度与动态规划对暴力枚举的优势。

核心能力

  • 高亮显示每个单元格的两个依赖(跳过/选取),支持运行/单步控制、速度调节、随机物品组,最优值实时显示
  • 完全在浏览器中运行,无需注册,注重隐私
  • 直观展示 O(n·W) 伪多项式复杂度与动态规划对暴力枚举的优势

适用场景

适合网络工程师、运维工程师、IT 从业者及相关专业学习者日常使用。背包可视化全程在浏览器中完成,无需安装插件,可放心用于日常办公与排障。

常见问题

背包可视化是免费的吗?需要注册或安装吗?
背包可视化完全免费,无需注册、无需下载安装任何软件,用浏览器打开网页即可直接使用,也不限制使用次数。
背包可视化支持哪些功能?
高亮显示每个单元格的两个依赖(跳过/选取),支持运行/单步控制、速度调节、随机物品组,最优值实时显示;完全在浏览器中运行,无需注册,注重隐私;直观展示 O(n·W) 伪多项式复杂度与动态规划对暴力枚举的优势。
背包可视化适合哪些场景使用?
适合网络工程师、运维工程师、IT 从业者及相关专业学习者日常使用。