逆背包问题

Question

我正在尝试解决下一个任务： 给定一组物品，每个物品都有一个重量和一个价值，确定给定总价值的背包最小承载能力。

例如 输入：

item1: w = 3.4, v = 3
item2: w = 0.4, v = 1
total value = 7

输出：

我们应该采取：

item1 x0, item2 x7

对于使用动态规划的通用算法，我应该使用什么

minimal capacity = 0 * 3.4 + 0.4 * 7 = 2.8
total value = 7

递归公式？谁能举一个用微小的输入数据解决这个问题的例子吗？

PS 抱歉我的英语。

Answer 1

传统的（最大化）背包算法应该可以正常工作。只需将所有出现的 max 替换为 min，您就应该差不多了。另一种看待这一问题的方法是使用负成本，因此最小化变成最大化（不过，您需要特别注意空的情况）。