一个组包含一组实体,每个实体都有一个值。
每个实体都可以属于多个组。
问题:找到最大的 N 个组,其中每个实体在结果中出现不超过一次。如有必要,可以将实体排除在组之外。
Example:
Entities with values:
A = 2
B = 2
C = 2
D = 3
E = 3
Groups
1: (A,B,C) total value: 2+2+2 = 6
2: (B,D) total value: 2 + 3 = 5
3: (C,E) total value: 2 + 3 = 5
4: (D) total value: 3
5: (E) total value: 3
**Answers**:
Largest 1 group is obviously (A,B,C) with total value 6
Largest 2 groups are (B,D), (C,E) with total value 10
Largest 3 groups are either {(A,B,C),(D),(E)}, {(A,B),(C,E),(D)} or {(A,C), (B,D), (E)} with total value 12
算法的输入数据应该是:
- 一组具有值的实体
- 包含一个或多个实体的组
- 结果中的组数
如果有多个答案,那么找到其中一个就足够了。
我举个例子是想把问题弄清楚,实践中实体的数量应该少于50个左右,组的数量应该少于实体的数量。要查找的 N 个组的数量将在 1 到 10 之间。
我目前正在通过生成 N 组的所有可能组合来解决这个问题,排除包含重复实体的结果,然后选择总值最大的组合。这当然是非常低效的,但我无法理解如何以更有效的方式获得一般结果。
我的问题是是否有可能以更有效的方式解决这个问题,如果可以,如何解决?非常感谢任何提示或答案。
编辑
明确地说,在我的解决方案中,我生成了“假”组,其中重复的实体被排除在“真实”组之外。在示例实体 (B, C, D, E) 中是重复的(存在于多个组中。然后对于组 1 (A,B,C) 我添加假组 (A,B),(A,C) ,(A) 到我为其生成组合的组列表。
最佳答案
这个问题可以表述为一个线性整数规划。虽然整数规划在复杂性方面不是非常高效,但它可以非常快速地处理如此多的变量。
下面是我们如何将这个问题转化为整数规划。
令 v
为大小为 K
的向量,表示实体值。
令 G
为定义组的 K x M
二进制矩阵:G(i,j)=1
表示实体 i
属于组 j
并且 G(i,j)=0
否则。
设x
为大小为M
的二元向量,代表组的选择:x[j]=1
表示我们选择组 j
。
设y
是一个大小为K
的二元向量,表示包含实体:y[i]=1
表示实体i
包含在结果中。
我们的目标是选择 x
和 y
以便在以下条件下最大化 sum(v*y)
:
G x >= y
...所有包含的实体必须至少属于所选组之一sum(x) = N
... 我们恰好选择了 N 个组。
下面是 R 中的实现。它使用 lpSolve
库,lpsolve 的接口(interface).
library(lpSolve)
solver <- function(values, groups, N)
{
n_group <- ncol(groups)
n_entity <- length(values)
object <- c(rep(0, n_group), values)
lhs1 <- cbind(groups, -diag(n_entity))
rhs1 <- rep(0, n_entity)
dir1 <- rep(">=", n_entity)
lhs2 <- matrix(c(rep(1, n_group), rep(0, n_entity)), nrow=1)
rhs2 <- N
dir2 <- "="
lhs <- rbind(lhs1, lhs2)
rhs <- c(rhs1, rhs2)
direc <- c(dir1, dir2)
lp("max", object, lhs, direc, rhs, all.bin=TRUE)
}
values <- c(A=2, B=2, C=2, D=3, E=3)
groups <- matrix(c(1,1,1,0,0,
0,1,0,1,0,
0,0,1,0,1,
0,0,0,1,0,
0,0,0,0,1),
nrow=5, ncol=5)
rownames(groups) <- c("A", "B", "C", "D", "E")
ans <- solver(values, groups, 1)
print(ans)
names(values)[tail(ans$solution, length(values))==1]
# Success: the objective function is 6
# [1] "A" "B" "C"
ans <- solver(values, groups, 2)
print(ans)
names(values)[tail(ans$solution, length(values))==1]
# Success: the objective function is 10
# [1] "B" "C" "D" "E"
ans <- solver(values, groups, 3)
print(ans)
names(values)[tail(ans$solution, length(values))==1]
# Success: the objective function is 12
# [1] "A" "B" "C" "D" "E"
下面是看看它如何处理大问题。它在一秒钟内完成。
# how does it scale?
n_entity <- 50
n_group <- 50
N <- 10
entity_names <- paste("X", 1:n_entity, sep="")
values <- sample(1:10, n_entity, replace=TRUE)
names(values) <- entity_names
groups <- matrix(sample(c(0,1), n_entity*n_group,
replace=TRUE, prob=c(0.99, 0.01)),
nrow=n_entity, ncol=n_group)
rownames(groups) <- entity_names
ans <- solver(values, groups, N)
print(ans)
names(values)[tail(ans$solution, length(values))==1]
关于algorithm - 我怎样才能更有效地编写这个组合算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44730820/