algorithm - 是否有最佳算法来查找行的子集，其总和位于指定的间隔内？

Question

我有一个矩阵，40 行 8 列，具有非负 float ，并且有 16 个浮点阈值:

S_min1, S_min2, ..., S_min8
S_max1, S_max2, ..., S_max8

我需要找到行的子集，这样:

• 第一列的总和介于 S_min1 和 S_max1 之间
• 第二列的总和介于 S_min2 和 S_max2 之间
• ...
• 第八列的总和介于 S_min8 和 S_max8 之间

有什么办法可以避免穷举算法吗？因为遍历 10^12 组合看起来不太好。

Answer 1

看起来像是 linear programming 的任务.

您为每一行定义整数系数 0/1，它们的总和应在 1..40 范围内。

然后使用这些系数和单元格值以及您的阈值来定义不等式。

  A[1,1]*R[1] + A[1,2]*R[2] +... + A[1,40]*R[40] > S_Min1
  A[1,1]*R[1] + A[1,2]*R[2] +... + A[1,40]*R[40] < S_Max1
  ...

使用一些可用的 LP 求解器解决每个系数和的任务
(也许有一种方法可以避免遍历可能的总和，但我不知道合适的条件)