这是发布的问题的子集here https://stackoverflow.com/questions/16703082/crafting-a-linq-based-solution-to-determine-if-a-set-of-predicates-are-satisfied/16703389#16703389.
给定一组容量桶B={x1, x2, ..., xn}和一组装有一定体积液体的小瓶V={v1, v2, ..., vn }假设必须将小瓶全部倒入一个桶中，证明可以装满小瓶内容物的桶数的最佳方法是什么。允许溢出。
这里一些明显的不变量是桶的基数|B|必须小于或等于小瓶的基数|V|水桶的总体积Sum(B)必须小于或等于小瓶的总体积Sum(V)
这是一个众所周知的计算问题吗？如果是这样，是否可以设计一个简单的 LINQ 解决方案来用 C# 来表达这一点？
我觉得埃里克·利珀特 (Eric Lippert) 会在博客上讨论这一点；-)。
考虑此问题的一个实例，其中有两个相同大小的桶，并且 Sum(B) = Sum(V)。这意味着您需要将瓶子平均分配到两个桶中，否则一个桶会溢出，而另一个桶则没有足够的剩余量。这被称为分区问题 https://en.wikipedia.org/wiki/Partition_problem，并且已知它是 NP 完全的。
Edit:当然，NP完备性并不意味着问题无法解决，只是运行时间将与输入的大小（在本例中为最大桶大小的log2）成指数关系。
如果我们能找到装满一个桶（包括溢出）所需的最小液体量，那么解决问题的方法很简单，对每个桶执行此操作，然后从每个桶后的一组可用小瓶中取出用过的小瓶。
我们可以通过使用动态规划来做到这一点：
- 对于给定的桶 b，考虑所有大小为 0 到体积 (b) 的桶。
- 0号桶显然不需要液体
- For each size s, find a vial v such that:
- s-volume(v) 的解不使用 v
- （s-体积（v）所用液体量）+体积（v）最小化
- 最后，您将获得用于填充桶 b 的小瓶。然后，您只需从一组可用的小瓶中取出它们，然后移动到下一个桶。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
