java - 最大化多个桶的总和？

Question

有 180 个球。

有 70 个桶。

每个球的值(value)取决于它在哪个桶中:

ball1 = { 1, 14, 2, 3, 4 ... } //70 values in total for each bucket
ball2 = { 24, 2, 23, 2, 5 ... }
...

每个桶都有最大数量的球，但 70 个桶的球总数可以携带的是 180，即所有 180 个球都将完全适合。 (每个桶至少要装1个球)

{bucket1, 3} {bucket2, 1} { bucket3, 2} {bucket4, 1} ...

如何最大限度地利用球的位置？

我尝试了暴力破解，数了数排列后很快就后悔了。

Answer 1

这似乎是一个二分图最大权重匹配问题。棘手的部分是如何构造二分图，以便我们可以应用多项式时间算法来解决问题。

为了简化问题，假设我们有 3 个球和 2 个水桶:

Ball 1: {1, 10},
Ball 2: {9, 20},
Ball 3: {7, 9};

Bucket 1: 2
Bucket 2: 1

我想构建如下图:

主要思想是构造一个二元图，使得节点的左侧部分代表球，而另一部分是桶的节点。并且我们给与每个桶的容量一样多的节点，现在我们可以应用最大权重匹配算法来解决我们的问题。