最大化多个桶总和？

Question

有180个球.

有70个水桶.

每个球的值取决于它所在的桶:

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

我想构建如下图:

主要思想是构造一个双图,使节点的左侧部分代表球,而另一部分是桶的节点.我们提供与每个桶的容量一样多的节点,现在我们可以应用最大权重匹配算法来解决我们的问题.