我正试图决定解决我的问题的最佳方法，如下:
我有一组对象(大约3k-5k)，我想将它们唯一地分配给大约10个组(每个对象1个组)。每个对象都有一组等级，对应于它在每个组中的适合程度。每个组都有一个它可以管理的对象的容量(约束)。我的目标是使我的作业得到的总分数最大化。
例如，假设我有3个对象(o1, o2, o3)和2个组(g1,g2)，每个组最多有1个对象。现在假设成绩为:
1: g1=11, g2=8
o2: g1=10, g2=5
3: g1=5, g2=6
在这种情况下，为了获得最佳结果，g1应该得到o2, g2应该得到o1，总共得到10+8=18分。
请注意，对象的数量可能超过配额的总和(例如，将o3作为"剩余")，也可能无法满足配额。
我该如何解决这个问题(旅行推销员，某种加重的背包等)?在一台普通电脑上进行暴力破解需要多长时间?有没有标准的工具，如Matlab中的linprog函数，支持这类问题?
可以用最小成本流算法求解。该图表可以如下所示:
它应该是二部的。左边部分表示对象(每个对象有一个顶点)。右边部分表示组(每个组有一个顶点)。对于这对，在capacity = 1和cost = -grade的条件下，从左部分的每个顶点到右部分的每个顶点都有一条边。在capacity = 1和cost = 0的条件下，从源顶点到左部分的每个顶点都有一条边;在capacity =约束条件下，从右部分到汇聚顶点(汇聚和源是两个附加顶点)的每个顶点都有一条边，cost = 0。
答案是-the cheapest flow cost from the source to the sink。
可以用O(N^2 * M * log(N + M))时间复杂度来实现(使用带势的Dijkstra算法)(N是对象的数量，M是组的数量)
这可以用一个整数程序来解决。二进制变量x_{ij}表示对象i是否被分配给组j。目标最大化sum_{i,j} s_{ij}x_{ij}，其中s_{ij}是将i分配给j时相关的分数，x_{ij}是是否将i分配给j。您有两种类型的约束:
- sum_i x_{ij} <= c_j对于所有j，组的容量约束
- sum_j x_{ij} <= 1 for all i，限制对象最多分配给一个组
下面是如何在R中实现它的方法——R中的lp函数与matlab中的linprog函数非常相似。
# Score matrix
S <- matrix(c(11, 10, 5, 8, 5, 6), nrow=3)
# Capacity vector
cvec <- c(1, 1)
# Helper function to construct constraint matrices
unit.vec <- function(pos, n) {
ret <- rep(0, n)
ret[pos] <- 1
ret
}
# Capacity constraints
cap <- t(sapply(1:ncol(S), function(j) rep(unit.vec(j, ncol(S)), nrow(S))))
# Object assignment constraints
obj <- t(sapply(1:nrow(S), function(i) rep(unit.vec(i, nrow(S)), each=ncol(S))))
# Solve the LP
res <- lp(direction="max",
objective.in=as.vector(t(S)),
const.mat=rbind(cap, obj),
const.dir="<=",
const.rhs=c(cvec, rep(1, nrow(S))),
all.bin=TRUE)
# Grab assignments and objective
sln <- t(matrix(res$solution, nrow=ncol(S)))
apply(sln, 1, function(x) ifelse(sum(x) > 0.999, which(x == 1), NA))
# [1] 2 1 NA
res$objval
# [1] 18
虽然这是用二元变量建模的，但它可以相当有效地求解积分容量