[几天前,我正在阅读有关分数背包问题的贪心算法和动态规划,并且我发现可以使用贪心方法最佳地解决该问题。任何人都可以通过动态编程方法给出示例或解决方案来解决此问题吗?
P.S:我知道贪婪方法是解决此问题的最佳方法,但我想知道动态编程如何解决此问题。
是的,您可以通过动态编程解决问题。
Let f(i, j)
表示可使用容量为i
的背包使用前j
个元素获得的最大总价值。
如果您熟悉0-1背包问题,那么您可能会记得我们具有完全相同的功能。但是,0-1背包问题的重复发生率是f(i, j) = max{f(i - 1, j), V[i] + f(i - 1, j - W[i])}
(第一个参数考虑了不取索引为i
的商品的情况,第二个参数考虑了取了索引为i
的项目)。
在小背包问题中,我们被允许服用]数量的某些物品。因此,在f(i, j) = max{f(i - 1, j), delta * V[i] f(i - 1, j - delta * W[i])
的所有可能值上,我们的重复率看起来像delta
,其中delta
代表我们要提取的物品的数量。
现在,如果以足够小的增量增加delta
,您应该会得到正确的答案。