背包变化 - 最小总价值超过“W”；
给定通常的 n 组项目（例如，每组都不受限制），具有权重和值：
w1, v1
w2, v2
...
wn, vn
以及目标权重 W，我需要选择项目，以使总重量 重量至少 W 并且总价值最小化。
在我看来，这就像一个变体（或者在某种意义上相反） 整数/无界背包问题。对制定 DP 算法有何帮助 将不胜感激！
Given the usual n sets of items (each unlimited, say), with weights and values:
w1, v1
w2, v2
...
wn, vn
and a target weight W, I need to choose items such that the total
weight is at least W and the total value is minimized.
This looks to me like a variation (or in some sense converse) of the
integer/unbounded knapsack problem. Any help in formulating the DP algorithm
would be much appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
让
TOT = w1 + w2 + ... + wn。在这个答案中我将描述第二个包。我将把原始的表示为“袋子”，将附加的表示为“背包”
用所有元素填充袋子，并开始从中排除元素，“填充”一个大小为 at 的新背包最多的
TOT-W，具有尽可能高的价值！您遇到了一个常规的背包问题，具有相同的元素，并且袋子大小为TOT-W。证明：
假设您有 k 个元素的最佳解决方案：
e_i1,e_i2,...,e_ik，则包大小至少为W，这使得背包中排除的物品最多为TOT-W尺寸。此外，由于背包的价值在尺寸W下最小化，因此排除项目的价值在尺寸TOT-W下最大化，因为如果没有最大化，则有尺寸至少为W且价值较小的更好包。相反[假设您有最大的排除包]几乎是相同的。
let
TOT = w1 + w2 + ... + wn.In this answer I will describe a second bag. I'll denote the original as 'bag' and to the additional as 'knapsack'
Fill the bag with all elements, and start excluding elements from it, 'filling' up a new knapsack with size of at most
TOT-W, with the highest possible value! You got yourself a regular knapsack problem, with same elements, and bag size ofTOT-W.Proof:
Assume you have best solution with k elements:
e_i1,e_i2,...,e_ik, then the bag size is at least of sizeW, which makes the excluded items knapsack at most at sizeTOT-W. Also, since the value of the knapsack is minimized for sizeW, the value of the excluded items is maximized for sizeTOT-W, because if it was not maximized, there would be a better bag of size at leastW, with smaller value.The other way around [assuming you have maximal excluded bag] is almost identical.
不太确定，但这可能有用。将这些值视为您拥有的值的-ve。 DP 公式将尝试找到该权重的最大值，在这种情况下这将是最小的负值。一旦你有了一个值，就可以得到最终的答案。
Not too sure, but this might work. Consider the values to be the -ve of the values you have. The DP formulation would try to find max value for that weight which would be the least negative value in this case. Once you have a value, take a -ve of it for the final answer.