algorithm - 我怎样才能更有效地编写这个组合算法？

Question

一个组包含一组实体，每个实体都有一个值。

每个实体都可以属于多个组。

问题:找到最大的 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) 到我为其生成组合的组列表。

Answer 1

这个问题可以表述为一个线性整数规划。虽然整数规划在复杂性方面不是非常高效，但它可以非常快速地处理如此多的变量。

下面是我们如何将这个问题转化为整数规划。令 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]