0/1 背包问题可视化工具
以动画方式展示 0/1 背包问题的动态规划（dynamic programming）过程——逐格填充 DP 表格，高亮显示每个格子依赖的前置格子，并支持逐步操作。直接在浏览器中运行。
伪代码
Press Run to animate the algorithm.
Time · Space
使用方法
- 1 点击「运行」按钮，逐格填充动态规划表格。
- 2 每一行代表一件物品；每一列代表从 0 到 W 的某个容量值。
- 3 每个格子的值取「跳过该物品」（对应上方蓝色格子）与「选取该物品」两者中的较大值。
- 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 时能获得的最大价值，通过比较「跳过该物品」与「选取该物品」两种情况取最大值计算得出。表格右下角的格子即为最优解。
0/1 背包问题可视化工具 是 Zerethon Tools 提供的免费 算法 工具。以动画方式展示 0/1 背包问题的动态规划（dynamic programming）过程——逐格填充 DP 表格，高亮显示每个格子依赖的前置格子，并支持逐步操作。直接在浏览器中运行。. 完全在浏览器中运行 — 无需注册，无需上传。
- 分类
- 算法
- 价格
- 免费
- 隐私
- 基于浏览器
- 注册
- 无需
隐私
除非另有说明，否则你的数据永远不会离开浏览器。0/1 背包问题可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。
刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Dynamic Programming →
相关工具
冒泡排序可视化工具
带动画演示的冒泡排序模拟器，提供单步执行、速度调节、自定义输入数据、实时比较/交换计数器以及伪代码同步高亮。完全在浏览器中运行。
打开工具插入排序可视化工具
动画演示插入排序算法，支持单步执行、速度调节、自定义输入数据，并实时显示比较/写入次数与伪代码高亮。完全在浏览器本地运行。
打开工具选择排序可视化工具
以动画方式演示选择排序（Selection Sort），提供逐步执行、速度调节、自定义输入数据、实时的比较/交换计数器以及伪代码展示。完全在浏览器本地运行。
打开工具归并排序可视化工具
带动画演示的归并排序模拟器，支持单步执行、速度调节、自定义输入数据、实时比较/写入计数器以及伪代码高亮显示。完全在浏览器中运行。
打开工具在 Zerethon Social 上创作、分享与成长
免费注册。赚取积分，收集成就，与全球创作者建立联系。