如何更有效地从 n 个集合中找到满足给定条件的最小组合？

Question

我们有 N 组三元组，比如

1. { (4; 0,1), (5 ; 0.3), (7; 0,6) }
2. { (7; 0.2), (8 ; 0.4), (1 ; 0.4) }
...
N. { (6; 0.3), (1; 0.2), (9 ; 0.5) }

并且只需要从每个三元组中选择一对，这样pair中第一个成员的总和将是最小的，而且我们有一个条件，即pair中第二个成员的总和必须不小于a给定P号。

我们可以通过对所有可能的配对组合及其第一个成员的总和（3 ^ N 组合）进行排序来解决这个问题，并在该排序列表中选择第一个也满足第二个条件的组合。你能帮忙提出一个更好的、更重要的解决这个问题的方法吗？

Answer 1

如果你的三元组中的值没有限制，那么我们将面临一个相当通用的 integer programming problem 版本，更具体地说是一个 0-1 线性规划问题，因为它可以表示为一个系统每个系数为 0 或 1 的方程组。您可以在 wiki 页面上找到可能的方法，但通常没有针对此问题的快速简便的解决方案。

或者，如果每对的第二个数字（需要总和为 >= P 的数字）的范围足够小，我们可以将其视为类似于 [=33] 的动态规划问题=] 问题。 "Small enough" 有点难定义，因为原始数据有非整数。如果它们是整数，那么我将描述的解决方案的算法复杂度是 O(P * N)。对于非整数，首先需要将它们以及 P 乘以一个足够大的数，从而将它们转换为整数。在您的示例中，每个数字的精度为零后 1 位，因此乘以 10 就足够了。因此，实际的复杂度是 O(M * P * N)，其中 M 是所有东西乘以得到整数的因子。

在此之后，我们实质上是在解决一个修改后的背包问题：我们不是从上面约束重量，而是从下面约束它，并且在每一步我们都从三元组中选择一对，而不是决定是否是否将物品放入背包。

让我们定义一个函数 minimum_sum[i][s]，它在值 i, s 处表示我们可以实现的最小可能总和（我们采用的每对中的第一个数字）如果第二个数字的总和被采用到目前为止等于 s 并且我们已经考虑了前 i 个三胞胎。此定义的一个例外是 minimum_sum[i][P] 也具有所有超过 P 的总和的最小值。如果我们可以计算这个函数的所有值，那么 minimum_sum[N][P] 就是答案。函数值可以这样计算：

minimum_sum[0][0]=0, all other values are set to infinity
for i=0..N-1:
  for s=0..P:
    for j=0..2:
      minimum_sum[i+1][min(P, s+B[i][j])] = min(minimum_sum[i+1][min(P, s+B[i][j])], minimum_sum[i][s] + A[i][j]

A[i][j]表示第i个三元组的第j对中的第一个数，B[i][j]表示同一个三元组的第二个数。

如果 N 很大，但 P 很小，并且 B 的精度不太高，则此解决方案是可行的。例如，如果 N=50，则几乎没有希望计算出 3^N 的可能性，但是对于 M*P=1000000，这种方法的工作速度会非常快。

Python 上面想法的实现：

def compute(A, B, P):
  n = len(A)
  # note that I use 1,000,000 as “infinity” here, which might need to be increased depending on input data
  best = [[1000000 for i in range(P + 1)] for j in range(n + 1)]
  best[0][0] = 0
  for i in range(n):
    for s in range(P+1):
      for j in range(3):
        best[i+1][min(P, s+B[i][j])] = min(best[i+1][min(P, s+B[i][j])], best[i][s]+A[i][j])
  return best[n][P]

测试：

A=[[4, 5, 7], [7, 8, 1], [6, 1, 9]]
# second numbers in each pair after scaling them up to be integers
B=[[1, 3, 6], [2, 4, 4], [3, 2, 5]]

In [7]: compute(A, B, 0)
Out[7]: 6

In [14]: compute(A, B, 7)
Out[14]: 6

In [15]: compute(A, B, 8)
Out[15]: 7

In [20]: compute(A, B, 13)
Out[20]: 14

如何更有效地从 n 个集合中找到满足给定条件的最小组合？

How more effectively find the minimal composition from n sets that satisfies the given condition?

algorithm

combinations

combinatorics