algorithm - 如何最大限度地减少在仓库之间移动 cargo 的总距离？

Question

第1天有N个仓库存储了Q[i]数量的一件商品。第2天，每个仓库的需求量为Q'[i]。所以基本上项目必须在仓库之间移动才能满足约束。仓库之间的距离是已知的。哪类算法可以解决这个问题？任何指针？目标是最大限度地减少 cargo 运输的距离。

Answer 1

这是一个用最小成本最大流算法解决的经典问题。您可以通过添加两个额外的顶点来扩充图形:源和汇。从源到原始图的所有顶点，您添加一条容量等于 Q[i] 且成本为零的边。从原始图的每个顶点向汇点添加一条边，其容量等于 Q'[i] 且成本为零。对于原始图的顶点之间的边，将容量设置为无穷大，并将成本设置为相应仓库之间的距离，然后计算最小成本最大流量。原始图的顶点之间的流动将告诉您在这两个仓库之间转移多少 cargo 。

一些链接:

1. wikipedia article关于min-cost max-flow

2. 很好presentation (他们那里的问题和你的类似但不完全相同)

3. 这是一个 great article具有非常好的实现的细节