几天前，我读到关于分数背包问题的贪婪算法和动态规划的文章，我看到这个问题可以用贪婪方法得到最佳解决。任何人都可以举一个例子或解决方案来用动态规划方法解决这个问题吗？
PS：我知道贪婪方法是解决这个问题的最好方法，但我想知道动态编程如何解决这个问题。
是的，你可以用动态编程来解决这个问题。
让我们f(i, j)表示使用容量为j的背包使用前i个元素可以获得的最大总值。
如果你熟悉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，您应该得到正确的答案。