我们有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) }
并且需要从每个三元组中仅选择一对，这样一对中的第一对成员的总和将是最小的，但是我们也有一个条件，即一对第二中的成员之和必须不少于给定的P数。
我们可以通过将所有可能的对组合与它们的第一个成员的和（3 ^ N个组合）进行排序来解决此问题，然后在该排序列表中选择第一个也满足第二个条件的组合。您能帮忙提出一个更好，更简单的解决方案吗？
如果三元组内部的值没有限制，那么我们将面临一个非常普通的整数规划问题，更具体地说是0-1线性规划问题，因为它可以表示为方程组，每个系数为0或1.您可以在Wiki页面上找到可能的方法，但是通常没有解决此问题的快捷方法。
或者，如果每对的第二个数字（需要加和的数字>= P）在足够小的范围内，我们可以将其视为类似于背包问题的动态编程问题。“足够小”很难定义，因为原始数据具有非整数。如果它们是整数，那么我将描述的解决方案的算法复杂度为O(P * N)。对于非整数，首先需要将它们以及乘以P足够大的数字，然后将它们转换为整数。在您的示例中，每个数字的精度为零后的1位数字，因此乘以10就足够了。因此，实际的复杂度为O(M * P * N)，其中M是将所有事物相乘以获得整数的因子。
此后，我们实质上是在解决一个改良的背包问题：不是从上方约束重量，而是从下方约束重量，并且在每个步骤中，我们都从三元组中选择一对，而不是决定是否将一件物品放入背囊与否。
让我们定义一个函数minimum_sum[i][s]，该函数的at值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较小且Bs的精度不太高。例如，如果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
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句