栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

从N个项目中选择M个项目,以使完成这些M个项目的任务花费的时间最少

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

从N个项目中选择M个项目,以使完成这些M个项目的任务花费的时间最少

通过贪婪方法求解(权重计算+截止日期排序)

这是解决此问题的贪婪方法,希望对您有所帮助。祝好运!

由于项目中的每个任务都需要时间T才能完成,因此我们可以将其视为这些任务(A,B和C)的“最后期限”。我们可以将这些截止日期可视化,就好像它们是插槽阵列/系列中的“插槽”一样。

为了可视化这些截止日期,请考虑以下示例;

项目2的任务A;

0__A__1__A__2__A__3

项目1的任务C;

0__C__1__C__2

让我们现在考虑一下;我们的手0__1__2__ … __K内有K个“插槽”,该问题要求我们尽可能减少插槽的使用量。

为了更好地可视化问题,从您的说明中得到的另一个示例是,当您选择item1和item3时,我们的广告位采用了这种形式;

item1 + item3“截止时间槽占用”

0_A_1_A_2_A_3_B_4_B_5_C_6_C_7

前三个插槽被占用,因为item3的任务A比item1长3个单位。任务B仅在完成“较长”任务A后才能启动,因此从插槽号3开始。

因此问题就变成了这个。在我们的广告位中填满最少要使用的广告位。因此,我们将对此问题采取贪婪的态度。

  • 从我们要从N个项目中选择的M个项目中找到单独的“最后期限广告位”

在示例中,您提供了;

对于项目1;

0_A_1_B_2_B_3_C_4_C_5

占用5个插槽

对于项目2; 占用8个插槽

对于第3项; 占用6个插槽

对于itemX; P插槽已占用,等等。

在知道每个项目对任务时间要求的插槽数量之后,我们将在N个项目任务时间之内检查M个 减法 项作为项目的组合,以获取最小的数量。

例; 当M = 2时选择M个项目;

Item1-Item2 = 5;

Item1-Item3 = 3;

Item2-Item3 = 4;

**编辑; 项目1-项目2对应于所选项目数量组合中的减法绝对值;例如,如果M = 2;| a1-a2 | + | b1-b2 | + | c1-c2 |

因此,对于M = 2个选择,我们取最小值3,这导致我们选择Item1和Item3作为解决方案。

此数字将为我们提供所使用的最小插槽数。因此,这导致我们找到解决方案。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/574297.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号