3

这是此处发布的问题的一个子集发布的问题的一个子集。

给定一组容积桶B={x1, x2, ..., xn}和一组装有容积液体的小瓶 V={v1, v2, ..., vn }小瓶，假设必须将小瓶全部倒入一个桶中，那么证明桶的数量可以装满小瓶的内容物的最佳方法是什么。允许溢出。

这里一些明显的不变量是桶的基数|B|必须小于或等于小瓶的基数，|V|并且桶的组合体积Sum(B)必须小于或等于小瓶的组合体积Sum(V)

这是一个众所周知的计算问题吗？如果是这样，是否可以制作一个简单的 LINQ 解决方案来用 C# 表达这一点？

我觉得这是 Eric Lippert 会写博客的东西；-)。

4

1 回答 1

3

考虑这个问题的一个例子，你有两个大小相同的桶，并且 Sum(B) = Sum(V)。这意味着您需要将小瓶平均分配到两个桶上，否则一个会溢出，而另一个则没有足够的空间。这称为分区问题，并且已知它是 NP 完全的。

编辑： 当然，NP-completeness 并不意味着问题无法解决，只是运行时间将是输入大小的指数（在这种情况下，最大存储桶大小的 log2）。

如果我们能找到装满一个桶所需的最少液体量（包括溢出），那么解决这个问题很简单，只需对每个桶执行此操作，然后在每个桶之后从一组可用的小瓶中取出用过的小瓶。

我们可以通过使用动态规划来做到这一点：

  • 对于给定的桶 b，考虑所有大小为 0 的桶，直到 volume(b)。
  • 0号桶显然不需要液体
  • 对于每个尺寸 s，找到一个小瓶 v 使得：
    • s-volume(v) 的解不使用 v
    • （用于s-volume(v)的液体量）+volume(v)最小化
  • 在所有这一切结束时，您将拥有用于填充桶 b 的小瓶。然后，您只需从一组可用的小瓶中取出它们，然后移至下一个桶。
于 2013-05-24T21:22:35.807 回答