algorithm - 效用最大化分配

Question

我将其发布在计算机科学部分，但没有人回复 :(。任何帮助将不胜感激 :)。

有一个大小为 MxN 的网格。 M~20000 和 N~10。所以 M 非常大。因此，一种方法是查看并排放置的 N 个大小为 M 的网格 block 。接下来假设有 K 个用户，每个用户都有一个 MxN 的效用矩阵，其中每个元素提供用户在分配给该网格元素时将获得的效用。分配需要以每个分配的用户总效用必须超过每个网格 block 中的某个阈值效用 U 的方式进行。假设只能为一个用户分配一个网格元素。 最多可以分配多少用户？。 (所以如果一些用户没有分配也没关系)。

第 2 级:现在假设对于每个用户，N 个 block 中至少有 n 个必须超过效用阈值 U。对于这个问题，可以分配的最大用户数是多少。

当然，由于 K^(MN) 的复杂性，暴力搜索在这里没有用。我猜测某种动态编程方法可能是可行的。

Answer 1

据我了解，问题可以建模为 Maximum Bipartite Matching问题，可以使用 Hungarian algorithm 有效解决.在左侧分区 L 中，创建 K 节点，每个用户一个。在右分区 R 中，创建 L*M*N 节点，每个节点对应网格中的每个单元格。由于边为每个 l in L 和 r in R 创建边，成本等于将用户 l 分配给网格单元的成本r。