假设有常见的n个物品集合（每个集合数量不限），其中包括它们的权重和价值：
w1, v1
w2, v2
...
wn, vn
给定一组物品，每个物品有一个重量 w 和一个价值 v，以及一个目标重量 W，需要选择物品使得总重量至少为 W 且总价值最小化。
这看起来像是整数/无限背包问题的一个变种（或在某种意义下的相反情况）。非常感谢任何有助于制定 DP 算法的帮助！
变形背包问题 - 最小总价值超过“W”
16
- ragebiswas
2个回答
35
令 TOT = w1 + w2 + ... + wn。
在这个答案中，我将描述第二个袋子。我将原始袋子称为“bag”，将额外的袋子称为“knapsack”。
首先将所有元素放入袋子中，然后开始从中排除元素，用最高可能价值的元素“填充”大小最多为 TOT-W 的新背包！你就得到了一个常规的背包问题，具有相同的元素和一个大小为TOT-W的袋子。
证明：
假设您有k个元素的最佳解决方案：e_i1,e_i2,...,e_ik，则袋子大小至少为 W，这使得被排除的物品的背包大小最多为TOT-W。此外，由于背包的价值对于大小W是最小化的，被排除物品的价值对于大小TOT-W是最大化的，因为如果它不是最大化的，那么会有一个至少大小为W的更好的袋子，其价值更小。
另一种情况[假设你有最大被排除的背包]几乎相同。
- amit
2
4遇到相同的问题，这个解决方案非常优雅。我真的很印象深刻。干得好。 - seth
只是一个简短的说明，这个解决方案对于无界背包问题是不适用的。 - Timmy Chan
0
不太确定，但这可能有效。将值视为您拥有的值的负数。DP公式将尝试找到该重量的最大值，这在这种情况下将是最小的负值。一旦您获得一个值，请取其负数作为最终答案。
- shobhit
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接