跳到主要内容
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 时能获得的最大价值，通过比较「跳过该物品」与「选取该物品」两种情况取最大值计算得出。表格右下角的格子即为最优解。

功能特性

DP table animation

Watch the value table fill in as each item and capacity are considered.

Complexity

Time & space: O(nW) (pseudo-polynomial). The problem is NP-hard in general.

100% private

Runs entirely in your browser — nothing is uploaded.

示例

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

    Learn dynamic programming

    See how overlapping subproblems build the optimal value.

  2. 2

    Resource allocation

    Model choosing items under a weight or budget limit.

  3. 3

    Pseudo-polynomial insight

    Understand why O(nW) isn't truly polynomial.

概要

Zerethon's 0/1 knapsack visualizer animates the dynamic-programming solution in your browser, filling a table of best values by item and remaining capacity. It runs in O(nW) time and O(nW) space (n items, capacity W) — pseudo-polynomial, since W is exponential in its bit length; the 0/1 knapsack problem is NP-hard in general.

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

References

隐私

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

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

相关工具

冒泡排序可视化工具

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

打开工具

插入排序可视化工具

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

打开工具

选择排序可视化工具

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

打开工具

归并排序可视化工具

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

打开工具

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

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

免费试用 Zerethon