algorithm - 离散优化算法

Question

我正在尝试确定解决我的问题的最佳方法，如下所示:

我有一组对象(大约 3k-5k)，我想将其唯一分配给大约 10 个组(每个对象 1 个组)。每个对象都有一组等级，对应于它在每个组中的适合程度。每个组都有它可以管理的对象的容量(约束)。我的目标是最大限度地提高我的作业获得的总成绩。

例如，假设我有 3 个对象(o1、o2、o3)和 2 个带帽的组(g1、g2)。每个 1 个对象。现在假设成绩是:

o1: g1=11, g2=8

o2: g1=10, g2=5

o3: g1=5, g2=6

在那种情况下，为了获得最佳结果，g1 应该接收 o2，g2 应该接收 o1，总共产生 10+8=18 分。

请注意，对象的数量可能会超过配额的总和(例如，将 o3 作为“剩余”)或未达到配额。

我应该如何解决这个问题(旅行推销员，一种加重的背包等)？在普通计算机上暴力破解需要多长时间？是否有任何标准工具(例如 Matlab 中的 linprog 函数)支持此类问题？

Answer 1

可以用最小成本流算法解决。该图可能如下所示:

应该是双向的。左侧部分表示对象(每个对象一个顶点)。右侧部分代表组(每个组一个顶点)。从左侧部分的每个顶点到右侧部分的每个顶点都有一条边，capacity = 1 且 cost = 这对的等级。从源顶点到左侧部分的每个顶点也有一条边，capacity = 1 且 cost = 0，并且从右侧部分的每个顶点都有一条边到接收器顶点(接收器和源是两个额外的顶点)，capacity = constraints for this group and cost = 0.

答案是——从源到汇的最便宜的流成本。

可以用 O(N^2 * M * log(N + M)) 时间复杂度(使用带势的 Dijkstra 算法)(N是对象的数量，M 是组的数量)。