algorithm - 用动态规划求解分数背包问题

Question

几天前，我正在阅读关于分数背包问题的贪心算法和动态规划，我看到这个问题可以用贪心方法最优地解决。任何人都可以举一个例子或解决方案来用动态规划方法解决这个问题吗？

PS：我知道贪心法是解决这个问题的最好方法，但我想知道动态规划是如何解决这个问题的。

标签： algorithmdynamic-programmingknapsack-problem

Answer 1

是的，你可以用动态规划解决这个问题。

让表示使用容量为 的背包的f(i, j)第一个元素可以获得的最大总值。 ij

如果您熟悉 0-1 背包问题，那么您可能还记得我们有完全相同的功能。然而，0-1 背包问题的重现是f(i, j) = max{f(i - 1, j), V[i] + f(i - 1, j - W[i])}（第一个参数考虑了我们没有在 index 处获取项目i的情况，第二个参数考虑了我们在 index 处获取项目的情况i）。

在分数背包问题中，我们可以拿一些物品的分数。f(i, j) = max{f(i - 1, j), delta * V[i] f(i - 1, j - delta * W[i])因此，在所有可能的 值上，我们的递归看起来像，delta其中delta表示我们正在服用的物品的数量。

现在，如果你delta以足够小的增量递增，你应该得到正确的答案。