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

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

grouping c++11 algorithm c++

Jordan · 技术社区 · 1 年前

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

我有一个场景,我有 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 回复 | 直到 1 年前

Cary Swoveland 1 年前

在给定的最小值和最大值之间选择一个设定点温度,使所选设定点落在每个项目的最小值与最大值之间的项目数量最大化的问题可以建模为整数线性规划问题,并用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求解器。

推荐文章

AstralHex · 矩阵乘法代码工作不正常

11 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

11 月前

Giogre · 为包含许多数值字段的简单“struct”重载比较运算符

11 月前

einpoklum · 定义一个并不真正提供now()函数的std::chrono Clock是“合法的”吗?

11 月前

Fishie · 作为类成员的智能指针是否仍然自动释放?[关闭]

11 月前

Die4Toast · 递归调用成员箭头运算符->

11 月前

Angle.Bracket · 如何用C++将UTF-8文件名写入MS Windows控制台?

11 月前

Anka HanÄ±m · 关于结构和动态数组地址的问题

12 月前

Adam Barnes · 我如何定义一个基于constexpr函数返回值进行限制的概念?

1 年前

user2138149 · 为什么我不能获取包含多个元素的结构体中某些元素的地址?[副本]

1 年前