分数背包+“生成的解决方案不到0/1背包最优值的1%。
我正在为即将到来的测试复习，想知道是否有人能重述问题的b部分。这是从分发的复习表中得到的文本，但我不确定b部分到底在问什么。我更直截了当地猜测“生成一个不到0/1背包问题最优值1%的解”是什么意思。
b)[10pts]举了一个有两个对象的例子，说明对分数背包问题使用的相同的贪婪方法（略加修改，如果贪婪方法选择的最后一个对象不适合，则忽略它）得到的解不到0/1背包问题最优解的1%。
共有1个答案
通常，贪婪启发式对背包问题非常有效。如果您只是随机提出一个小问题实例，那么应用贪婪启发式很可能会产生一个好的，甚至可能是最优的解决方案。（一个解决方案的质量是通过取它所包含的对象的总价值，并计算该总价值与最优解决方案所包含的对象的总价值的比率来衡量的。）
这个问题要求您想出一个讨厌的问题实例（即，一个带有值和权重的对象列表），它使贪婪的启发式非常混乱，以至于应用它会产生一个背包，其中只包含最优解所包含的值的1%。
-
我写了一个背包类，我用它来解决背包算法。这个类正在使用动态规划算法来解决这个问题。 我在代码中实现了一些优化，因此我使用线性O（W）空间来找到最大值，但当我试图找到见证时，我仍然需要O（nW）空间来保持布尔表。 有人能告诉我，是否有可能找到背包容量最大、空间较小、复杂度与O（nW）相同的证据，这里W是背包容量。 如果您认为代码中可能还有更多优化，请也告诉他们。
-
这里的一个明显问题是，对于我所考虑的维度，这种方法消耗的内存将超过可行的（需要空间，是元素数，是最大容量）。进一步研究，我发现提到了（例如，这里也参见Kellerer，Pferschy和Pisinger的“背包问题”）一个内存有效的方法来解决0-1背包。 我们首先将项目集合分成大小大致相等的两个子集。我们将这两个子集视为它们自己的背包问题，给定初始的最大权重，并以节省内存的方式为这两个子集确定最大
-
本文向大家介绍解决0-1背包问题的C ++程序，包括了解决0-1背包问题的C ++程序的使用技巧和注意事项，需要的朋友参考一下 在0-1背包问题中，给出了一组项目，每个项目都有一个权重和一个值。我们需要确定要包含在集合中的每个项目的数量，以使总重量小于或等于给定的限制，并且总值尽可能大。 输入项 输出结果 算法 范例程式码 输出结果
-
我对这个问题有点困惑。作为算法帮助我找到最大的利润从袋。但是这个算法并没有告诉我我应该拿哪一个项目会让我的利润最大。例如 n=4项，背包的容量M=8，利润=[15,10,9,5]，重量分别为w=[1,5,3,4]，当我解决这个问题时，我得到最大的利润为29 这里是解决方案[http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf] 但是我想知道我应该
-
在维基百科中，背包的算法如下： 我在网上找到的所有例子的结构都是一样的<我无法理解的是，这段代码是如何考虑到最大值可能来自较小的背包这一事实的？E、 如果背包容量为8，那么最大值可能来自容量7（8-1）<我找不到任何逻辑来考虑最大值可能来自较小的背包。这是错误的想法吗？
-
在我为0/1背包和无界背包签出的所有DP解决方案中，解决方案方法总是这样定义的： 0/1背包：取第n项或不取第n项，使总价值最大化。例如，0/1背包 无界背包：将第n个物品视为最后挑选的物品，或（n-1）个物品视为最后挑选的物品，使总价值最大化。例如，无界背包 但无界背包也可以使用0/1背包的逻辑来解决，只需稍加调整。我的意思是，对于0/1背包，我们执行以下操作（使用第一个链接中的代码）： 请注意