algorithm - 使用 LINQ 证明一组需求可以通过一组值来满足

Question

这是发布问题的子集 here .

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

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

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

我觉得这是 Eric Lippert 会在博客中讨论的内容 ;-)。

Answer 1

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

编辑:当然，NP 完全性并不意味着问题无法解决，只是运行时间会随着输入的大小(在本例中为最大桶大小的 log2)呈指数增长。

如果我们能找到装满一个桶所需的最小液体量(包括溢出)，解决这个问题很简单，只需对每个桶执行此操作，并在每个桶后从可用小瓶中取出用过的小瓶.

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

• 对于给定的 bucket b，考虑所有大小为 0 的 bucket，直到 volume(b)。
• 0 号桶显然不需要液体
• 对于每个尺寸 s，找到一个小瓶 v 使得:
  • s-volume(v)的解决方案没有使用v
  • (用于s-volume(v)) + volume(v)的液体量最小化
• 在这一切结束时，您将获得用于填充桶 b 的小瓶。然后，您只需从一组可用的小瓶中取出那些，然后转到下一个桶。