温度范围分组算法[修订]

Question

请注意，这是先前已关闭问题的更详细版本。

我有一个场景，我有

N

个物品（

N

是一个很大的数字），每个物品都有一个最低允许温度（

min_temp

）和一个最高允许温度（

max_temp

）。

我需要找到一个设定点温度，使该设定点位于

min_temp

和

max_temp

值之间的物品数量最大化。理想情况下，它会找到在设定点和兼容项目的最接近的最小/最大值之间提供最大缓冲的值（即出现波动时最安全的设定点）。

强力方法是以特定步长循环遍历可能的温度，例如：

float best_temp;
size_t best_num_items = 0;
for(float t = -60; t < 100; t += 0.1) {
    size_t num_items = 0;
    for(auto item: items) {
        if(t >= item.min_temp && t <= item.max_temp) {
            num_items++;
        }
    }
    if(num_items > best_num_items) {
        best_num_items = num_items;
        best_temp      = t;
    }
}

这将为我提供最佳设定点，但是（a）它显然效率极低，（b）它没有考虑到如上所述找到具有最大缓冲区的值，并且（c）它否定了所有可能的值步长之间。

我应该考虑一种非暴力的方法吗？

Answer 1

在给定的最小值和最大值之间选择设定点温度以最大化所选设定点落在每个项目的最小值和最大值之间的项目数量的问题可以建模为整数线性规划问题并使用 ILP 软件求解包。

模型的制定如下。

数据

• SP_l：最低设定点温度

• SP_h：最大设定点温度

• X_il：项目 i

  的最低温度

• X_ih：项目 i

  的最高温度

变量

• sp：等于设定点的连续变量

• x_i : = 1 如果项目 i 被选为组的一部分；否则= 0

混合整数规划

最大总和_ix_i

须遵守：

sp + (SP_h-X_ih)x_i <= SP_h 对于所有 i

-sp + (SP_l+X_il)x_i <= SP_l 对于所有 i

sp<= SP_h

-sp <= -SP_l

请注意，前两组约束分别源自以下内容。

sp <= X_ihx_i + SP_h(1-x_i)

sp >= X_ilx_i - SP_l(1-x_i)