algorithm - 动态规划或图算法，一个不错的问题

Question

代理在 n 生产者和 m 消费者之间工作。今年第i个生产者，生产了s_i个糖果，第j个消费者消费了b_j个糖果。对于销售的每一颗糖果，代理商都会获得 1 美元的返回。对于一些问题，定义了一个严格的规则，即生产者应该向任何生产者销售糖果，它们之间的距离不大于 100 KM(公里)。如果我们有所有生产者-消费者对的列表，它们之间的距离小于 100 KM，下面哪个算法是寻找最大 yield 的最佳算法？ (假设 s_i 和 b_j 可能变得非常大)。

1) Maximal Matching

2) Dynamic Programming

3) Maximum Flow 

4) 1 , 3

这是 2013 年 DS 类(class)期末考试的最后一道题。任何提示或想法？

Answer 1

据我了解，问题可以作为 Maximum Bipartite Matching 来解决，但是建模要求图形与原始输入相比相对较大；对于每条可行边 (s_i,b_j) 为生产者分区引入 s_i 节点，为消费者分区引入 b_j 并连接每个生产者节点到他们的每个消费者节点。

问题可以建模为 Maximum Flow Problem然而，在二分图上；每个可行边上的流 (s_i,b_j) 受到来自下方的 0 和来自上方的 min{s_i,b_j} 的约束，作为流量必须是非负的，但不能超过生产者和消费者的能力。

关于通过 Dynamic Prgramming 的解决方案，请考虑以下最大二分匹配的递推关系草图。设n 和m 分别表示第一个和第二个分区中的节点数。在第一个分区固定一个节点a； a 不匹配或与其邻居之一匹配；在任何一种情况下，都会评估每种可能性，递归地评估分区具有 n-1 和 m 或 n-1 和 的实例>m-1个节点，分别；做出这些选择中的最佳选择。

简而言之，显然所有提出的方法都产生了有效的解决方案；然而，作为网络流的建模似乎是最自然的。