algorithm - 背包的变化 - 超过“W”的最小总价值

Question

给定通常n的项目集（例如，每个项目都是无限的），具有权重和值：

w1, v1
w2, v2
...
wn, vn

和一个目标重量W，我需要选择总重量至少 W和总值最小的项目。

在我看来，这就像整数/无界背包问题的变体（或在某种意义上相反）。任何帮助制定 DP 算法将不胜感激！

Answer 1

让TOT = w1 + w2 + ... + wn.

在这个答案中，我将描述第二个包。我将原件表示为“包”，将附加件表示为“背包”

用所有元素填充袋子，并开始从中排除元素，“填充”一个最大尺寸为，价值最高的新背包TOT-W！你遇到了一个普通的背包问题，具有相同的元素，袋子大小为TOT-W.

证明：
假设你有 k 个元素的最佳解决方案：e_i1,e_i2,...,e_ik，那么袋子的大小至少是 size W，这使得排除的物品最多为 size TOT-W。此外，由于背包的值对于 size 是最小的W，所以排除项目的值对于 size 是最大化的TOT-W，因为如果它没有被最大化，那么至少会有一个更好的袋子，W价值更小。
反过来[假设你有最大的排除包]几乎是相同的。

Answer 2

不太确定，但这可能会奏效。将这些值视为您拥有的值的 -ve。DP 公式将尝试找到该权重的最大值，这在这种情况下将是最小的负值。一旦你有了一个值，就拿它作为最终答案。