跳到主要内容
Z

0/1 背包问题可视化工具

以动画方式展示 0/1 背包问题的动态规划（dynamic programming）过程——逐格填充 DP 表格，高亮显示每个格子依赖的前置格子，并支持逐步操作。直接在浏览器中运行。

免费 无需注册 客户端运行 注重隐私 Updated

/

伪代码

Press Run to animate the algorithm.

使用方法

  1. 1 点击「运行」按钮，逐格填充动态规划表格。
  2. 2 每一行代表一件物品；每一列代表从 0 到 W 的某个容量值。
  3. 3 每个格子的值取「跳过该物品」（对应上方蓝色格子）与「选取该物品」两者中的较大值。
  4. 4 表格右下角的格子就是能达到的最大价值。点击「随机」按钮可生成新的一组物品。

为什么使用此工具

  • 直观了解 0/1 背包问题如何通过动态规划求解，而非暴力穷举（brute force）。
  • 观察每个格子是如何由它所依赖的两个格子推导出来的。
  • 理解 O(n·W) 的运行时间相较于暴力穷举的指数级复杂度有何优势。
  • 完全在浏览器本地运行，无需注册，也不会上传任何数据。

常见问题

什么是 0/1 背包问题？

给定一组物品，每件物品都有各自的重量和价值，以及一个容量上限 W，需要从中选出一个子集（每件物品要么选、要么不选，不能重复选取），使得在总重量不超过 W 的前提下，总价值最大。

DP 表格是如何运作的？

dp[i][w] 表示使用前 i 件物品、容量为 w 时能获得的最大价值。每个格子的值等于 max(跳过该物品 = dp[i-1][w]，选取该物品 = dp[i-1][w-wi] + vi)。

这个算法的时间复杂度是多少？

时间复杂度为 O(n·W)，空间复杂度为 O(n·W)（可优化压缩至 O(W)）。这属于伪多项式（pseudo-polynomial）复杂度——在 W 较小时效率很高。

为什么叫做 0/1 背包问题？

每件物品要么被完整选取（1），要么被完全跳过（0）——不能只选取一部分，这一点与可以用贪心算法（greedy）求解的分数背包问题（fractional knapsack）不同。

什么是 0/1 背包问题可视化工具？

0/1 背包问题可视化工具以动画形式演示动态规划表格的填充过程，其中 dp[i][w] 表示使用前 i 件物品、容量为 w 时能获得的最大价值，通过比较「跳过该物品」与「选取该物品」两种情况取最大值计算得出。表格右下角的格子即为最优解。

功能特性

动态规划表动画演示

观察在依次考虑每个物品和容量时,价值表是如何被填充的。

复杂度

时间与空间复杂度:O(nW)(伪多项式)。该问题在一般情况下是 NP 难的。

100% 隐私保护

完全在你的浏览器中运行——不会上传任何数据。

示例

Input

items (w,v) = (10,60),(20,100),(30,120); capacity 50

Output

max value = 220 (take items 2 and 3, weight 50)

常见使用场景

  1. 1

    学习动态规划

    了解重叠子问题如何构建出最优价值。

  2. 2

    资源分配

    模拟在重量或预算限制下选择物品的场景。

  3. 3

    理解伪多项式

    理解为什么 O(nW) 并不是真正意义上的多项式时间。

概要

Zerethon 的 0/1 背包问题可视化工具在浏览器中动态演示动态规划求解过程,按物品和剩余容量逐步填充最优价值表。该算法的时间复杂度为 O(nW),空间复杂度也为 O(nW)(n 为物品数量,W 为容量)——这是一种伪多项式算法,因为 W 相对于其比特长度是指数级增长的;0/1 背包问题在一般情况下是 NP 难的。

分类
算法
价格
免费
隐私
基于浏览器
注册
无需

参考资料

隐私

除非另有说明，否则你的数据永远不会离开浏览器。0/1 背包问题可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。

刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Dynamic Programming →

相关工具

冒泡排序可视化工具

带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。

打开工具

插入排序可视化工具

动画演示插入排序算法，支持单步执行、速度调节、自定义输入数据，并实时显示比较/写入次数与伪代码高亮。完全在浏览器本地运行。

打开工具

选择排序可视化工具

以动画方式演示选择排序（Selection Sort），提供逐步执行、速度调节、自定义输入数据、实时的比较/交换计数器以及伪代码展示。完全在浏览器本地运行。

打开工具

归并排序可视化工具

带动画演示的归并排序模拟器，支持单步执行、速度调节、自定义输入数据、实时比较/写入计数器以及伪代码高亮显示。完全在浏览器中运行。

打开工具

在 Zerethon Social 上创作、分享与成长

免费注册。赚取积分，收集成就，与全球创作者建立联系。

免费试用 Zerethon