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

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 组的所有可能组合来解决这个问题，排除包含重复实体的结果，然后选择总值最大的组合。这当然是非常低效的，但我无法理解如何以更有效的方式获得一般结果。

我的问题是是否有可能以更有效的方式解决这个问题，如果可以，如何解决？非常感谢任何提示或答案。

编辑

明确地说，在我的解决方案中，我生成 "fake" 组，其中重复的实体被排除在 "real" 组之外。在示例实体 (B, C, D, E) 中是重复的（存在于多个组中。然后对于组 1 (A,B,C) 我添加假组 (A,B),(A,C) ,(A) 到我为其生成组合的组列表。

Answer 1

如果实体值始终为正，我认为您可以在不生成所有组合的情况下获得解决方案：

按最大元素、第二大元素、第 n 大元素对组进行排序。在这种情况下，您将拥有 3 个副本，因为最大的组有 3 个元素。

对于每个副本，从最大到最小进行一次传递，仅当组不包含您已添加的元素时才将其添加到解决方案中。这会产生 3 个结果，取最大的。除非权重可能为负，否则不应该有更大的可能解决方案。

这是 C# 中的实现

var entities = new Dictionary<char, int>() { { 'A', 2 }, { 'B', 2 }, { 'C', 2 }, { 'D', 3 }, { 'E', 3 } };
var groups = new List<string>() { "ABC", "BD", "CE", "D", "E" };
var solutions = new List<Tuple<List<string>, int>>();

for(int i = 0; i < groups.Max(x => x.Length); i++)
{
    var solution = new List<string>();
    foreach (var group in groups.OrderByDescending(x => x.Length > i ? entities[x[i]] : -1))
        if (!group.ToCharArray().Any(c => solution.Any(g => g.Contains(c))))
            solution.Add(group);

    solutions.Add(new Tuple<List<string>, int>(solution, solution.Sum(g => g.ToCharArray().Sum(c => entities[c]))));
}

solutions.Dump();
solutions.OrderByDescending(x => x.Item2).First().Dump();

输出：

Answer 2

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

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

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]

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

How can I write this combinatorics algorithm more efficiently?

algorithm

combinatorics

time-complexity