在背包里
重量
最佳可能

    物品

      更多关于背包问题

      背包问题

      你能背的重量有限,而每个物品都有重量和价值。拿哪些物品才能带走最多的价值?如果尝试所有组合,每多一个物品,工作量就翻一倍。一张以物品为行、以容量为列的表格,可以一格一格地找出最佳装法。 点按一个物品把它装进背包,再点按一次(无论它在背包里还是在架子上)就把它拿出来。背包按重量装满,几个方块显示你装入的美元与最佳可能值的对比。按“最佳装法”查看最佳背包。在面板中修改物品的千克数和美元数,添加或删除物品,并设置背包容量。“表格”视图展示动态规划如何找到最佳背包:按“播放”观看表格逐步填满,或按“单步”和“后退”一次走一步,拖动步骤滑块可跳到任意位置。每一行加入一个物品,每一列是一个以千克计的容量,每个格子存放能装下的最多美元。选中表格时,方向键逐步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

      它是如何运作的

      1. 点按物品箱把它们装进背包,看背包按千克重量逐渐装满。
      2. 试着达到以美元计的最高价值,或按“最佳装法”查看最佳装法。
      3. 打开“表格”视图并按播放,观看每个单元格在装入和不装某件物品之间做出选择。

      表格如何运作

      每一行加入一个物品,每一列是一个容量,从 0 到背包的容量。一个格子保存只用到该行为止的物品时,在该容量下能装下的最大价值。不用新物品时,就是上方的格子。用新物品时(如果装得下),就是该物品的价值加上剩余重量的最佳价值,这个值在上一行、向左移动该物品重量的位置。格子保留两者中较大的那个。第一行没有物品,全是 0。

      倒推出物品

      右下角的格子就是最佳价值。要找出物品,从那里开始,把它和上方的格子比较:如果相同,说明不需要最后一个物品;如果更大,说明该物品在背包里,于是减去它的重量,移到那一列。每次向上一行,直到第一行。应用用橙色显示这个倒推过程,并在表格下方列出装入的物品。

      常见问题

      0/1 背包问题中的 0/1 是什么意思?

      每个物品要么装一次,要么不装,既不能只装一部分,也不能装两次。如果物品可以分割,比如米粒,那么先装单位重量价值最高的就是最优的;这就是分数背包问题。

      为什么不先装单位重量价值最高的物品?

      因为整个的物品可能留下空隙。容量为 7,物品重量为 1、3、4、5,价值为 1、4、5、7 时,单位重量价值最高的是重量为 5 的物品,装入后只剩下装重量为 1 的物品的空间,总价值为 8。而重量为 3 和 4 的两个物品加起来价值 9。

      背包算法有多快?

      表格有(物品数 + 1)乘(容量 + 1)个格子,每个格子一步填好。容量小时很快,但容量可以是一个巨大的数,所以这个问题在一般情况下是 NP 困难的;这种表格方法被称为伪多项式时间算法。

      同一个物品能装两次吗?

      这里不能。在完全背包问题中,每个物品可以取任意多次;这时表格读取同一行左边的格子,而不是上一行的格子,就像找零钱应用中那样。

      会向任何地方发送数据吗?

      不会。所有计算都在你的浏览器中完成,你上次的设置保存在这个浏览器的本地存储中。

      准备好尝试了吗?

      在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

      前往编辑器