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

Question

几天前，我在读关于分数背包问题的贪婪算法和动态规划的书，我发现这个问题可以用贪婪方法得到最优解。谁能给出一个例子或解决方案来解决这个问题的动态规划方法？

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

Answer 1

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

让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，您应该会得到正确的答案。