时间戳

首页 > 解决方案 > 是否有最佳算法来查找行子集，总和在指定间隔内？

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

问题描述

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

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

我需要找到行的子集，例如：

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

标签： algorithm

解决方案

它看起来像是线性规划的任务。

您为每一行定义整数系数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 求解器解决每个系数总和的任务
（也许有一种方法可以避免循环遍历可能的总和，但我不知道合适的条件）

推荐阅读