将球分配到篮子的算法

Question

我心中有一个问题，我确信有一种有效的方法可以解决它，而无需使用暴力。这是我的问题：

我在房间里放置了 X 个球，并且房间里也放置了 Y 个篮子。每个篮子都有可容纳一定数量球的空间，每个篮子的空间可能有所不同。我想找到最小化每个球到篮筐的距离总和的组合。

举个例子：

3 个球 (B1-B2-B3)、2 个篮子 (Bk1-Bk2) 和 Bk1 有 2 个插槽（可容纳 2 个球），Bk2 有 1 个插槽。 可能的组合有：(Bk1[B1-B2] Bk2[B3]) (Bk1[B1-B3] Bk2[B2]) (Bk1[B2-B3] Bk2[B1])。 因此我们可以计算距离：Bk1->B1、Bk1->B2、Bk1->B3、Bk2->B1、Bk2->B2、Bk2->B3。 对于每个组合，我们可以计算距离之和并选择最小的。

但是这个问题是众所周知的问题的变体吗？已经有一个简洁的解决方案了吗？我希望如此，并且有人可以指点我。

Answer 1

这个问题可以使用最小成本流图算法以及使用线性规划

来解决

图法：

制作假源

S

和汇

T

使用零成本和容量 1 的边将

S

与球连接 使用零成本和大容量的边缘将篮子与

T

连接起来（比如

N_BALLS+1

）
使用容量为 1 的边将球与篮子连接起来，成本等于相应的距离
找到精确尺寸

N_Balls

的最小成本流 我修改了维基图片以提供精确的流量值（

w(e)

是距离）

C++实现

也许你可以在Python networkx库中找到合适的算法