动态规划或图算法，一个不错的问题
A Dynamic Programming or Graph Algorithm, a Nice Questions
代理在 n 生产者和 m 消费者之间工作。今年第 i 个生产者，生产 s_i 个糖果，第 j 个消费者消耗 b_j 个糖果。对于销售的每一颗糖果，代理商都会获得 1 美元的回报。对于某些问题，定义了一个严格的规则，即生产者应向任何距离不大于100 KM（公里）的生产者销售糖果。如果我们有所有生产者-消费者对的列表，它们之间的距离小于 100 KM，以下哪个算法是寻找最大收益的最佳选择？ （假设 s_i 和 b_j 可能变得非常大）。
1) Maximal Matching
2) Dynamic Programming
3) Maximum Flow
4) 1 , 3
这是 2013 年 DS 课程期末考试的最后一道题。任何提示或想法？
根据我的理解，问题可以作为 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 节点的实例；这些选择中最好的被采纳。
简而言之，显然所有提出的方法都产生了有效的解决方案；然而，建模为网络流似乎是最自然的。
代理在 n 生产者和 m 消费者之间工作。今年第 i 个生产者，生产 s_i 个糖果，第 j 个消费者消耗 b_j 个糖果。对于销售的每一颗糖果，代理商都会获得 1 美元的回报。对于某些问题，定义了一个严格的规则，即生产者应向任何距离不大于100 KM（公里）的生产者销售糖果。如果我们有所有生产者-消费者对的列表，它们之间的距离小于 100 KM，以下哪个算法是寻找最大收益的最佳选择？ （假设 s_i 和 b_j 可能变得非常大）。
1) Maximal Matching
2) Dynamic Programming
3) Maximum Flow
4) 1 , 3
这是 2013 年 DS 课程期末考试的最后一道题。任何提示或想法？
根据我的理解，问题可以作为 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 节点的实例；这些选择中最好的被采纳。
简而言之，显然所有提出的方法都产生了有效的解决方案；然而，建模为网络流似乎是最自然的。