变化对背包 - 最小的总价值超过了“W” [英] Variation on knapsack - minimum total value exceeding 'W'

问题描述

由于通常的 N 项目集（每一个无限的，说的），配重块和值：

Given the usual n sets of items (each unlimited, say), with weights and values:

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

和目标体重是W ，我需要选择的项目总这样 重量至少 是W ，总价值为最小

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.

这在我看来就像一个变化（或在某种意义上匡威）的 整数/无界背包问题。任何帮助制定规划算法 将是非常美联社preciated！

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!

推荐答案

让 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'

填充袋的所有元素，并开始从中排除的元素，填充'了一个新背包至多 TOT-W ，以尽可能高的价值！你拥有属于自己的普通背包问题，有相同的元素，以及包大小 TOT-W 。

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 of TOT-W.

证明：
假设您有k个元素最好的解决办法： e_i1，e_i2，...，e_ik ，然后将袋子大小至少为大小是W ，这使得排除的项目背包至多在尺寸 TOT-W 。此外，由于背包的价值是最小尺寸为是W 的排除的项目的价值最大化为大小 TOT-W ，因为如果它没有最大化，将有更好的包大小中的至少是W ，以较小的值。
周围的其他方法[假设你已经排除了最大的包]几乎是相同的。

Proof:
Assume you have best solution with k elements: e_i1,e_i2,...,e_ik, then the bag size is at least of size W, which makes the excluded items knapsack at most at size TOT-W. Also, since the value of the knapsack is minimized for size W, the value of the excluded items is maximized for size TOT-W, because if it was not maximized, there would be a better bag of size at least W, with smaller value.
The other way around [assuming you have maximal excluded bag] is almost identical.

这篇关于变化对背包 - 最小的总价值超过了“W”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！