如何更高效地编写组合算法？

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）是重复的（存在于多个组中）。然后，对于第一组（A、B、C），我将（A、B）、（A、C）和（A）等虚假组添加到我生成的组合列表中。

- Ponyboy

---

为什么你不能将A、B、C、D、E分组在一起，得到总数为12？ - zenwraight

如果我没有把问题表述清楚，我很抱歉。在这个例子中，1-5组可以被视为输入数据。 - Ponyboy

在这个例子中，当查找最大的3个组时，所有实体都被包括在内，此时“最大的N个组”，其中N>3是无关紧要的。 - Ponyboy

你能否添加一个使用“如果必要，实体可以从组中排除”的情况吗？ - Kota Mori

在查找最大的三个组时，可能的结果是：{(A,B),(C,E),(D)}。在这种情况下，实体C已从第一组中排除。 - Ponyboy

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的接口。

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]

- Kota Mori

---

非常感谢您提供如此优雅的解决方案，我已经使用ojalgo库在Java中实现了它，并且它运行良好。 - Ponyboy

很高兴听到这个消息。顺便说一句，我已经修正了笔误（我对lhs和rhs感到困惑）。行为没有改变。只是变量命名更加合适了。 - Kota Mori

Answer 2

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

按其最大元素、第二大元素、第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();

输出：

- gordy