代码之家 › 专栏 › 技术社区 › Jordan

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

grouping c++11 algorithm c++

Jordan · 技术社区 · 2 年前

请注意,这是之前一个封闭式问题的更详细版本。

我有一个场景,我有 N 项目( N 是一个大数字),每个项目都有一个最低允许温度( min_temp )以及最高允许温度( max_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)它否定了步长之间的所有可能值。

对此,我应该考虑一种非暴力的方法吗?

0 回复 | 直到 2 年前

Cary Swoveland 2 年前

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

模型的公式如下。

数据

服务提供商 _{字母 l(英语字母表中的第十二个字母)} :最低设定点温度
服务提供商 _h :最高设定点温度
十、 _il :项目i的最低温度
十、 _ih :项目i的最高温度

变量

sp:等于设定点的连续变量
x _我 :=1,如果项目i被选为组的一部分;else=0

混合整数程序

最大值 _我 x _我

从属于:

sp+(sp _h 十、 _ih )x _我 SP _h 对于所有我

-sp+(sp _{字母 l(英语字母表中的第十二个字母)} 十、 _il )x _我 SP _{字母 l(英语字母表中的第十二个字母)} 对于所有我

sp sp _h

-sp-sp _{字母 l(英语字母表中的第十二个字母)}

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

sp?X _ih x _我 +SP _h (1-x _我 )

这减少到:

sp?X _ih 如果x _我 1.

sp sp _h 如果x _我 = 0

同样地,

sp X _il x _我 -SP _{字母 l(英语字母表中的第十二个字母)} (1-x _我 )

这减少到:

sp X _il 如果x _我 1.

sp sp _{字母 l(英语字母表中的第十二个字母)} 如果x _我 = 0

查看@havish的回答 here 例如使用Python的ILP求解器。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前