从N个项目中选择M个项目，以使完成这些M个项目的任务花费的时间最少 [英] Select M items from N items such that completing these M item's tasks take the minimum time

问题描述

我正在尝试解决以下问题：
您得到了N个项目。每个项目包含三个任务A，B和C。完成任务A所需的时间为TA，任务B为TB，任务C为TC。现在，我们必须选择M项，以便以最少的时间完成这些M项的任务。规则如下：

I'm trying to solve the following problem: You are given N items. Each item contains three tasks A, B and C. The time required to complete task A is TA, task B is TB, task C is TC. Now, we must select M items such that completing these M item's tasks take the minimum time. And here are the rules:

1. 所有选中的M个项目同时操作，即所有M个项目的任务同时操作


2. 除非所有M个项目的任务A完成，否则无法启动任何选定项目的任务B


3. 除非已完成任务B的任务B，否则无法启动任何选定项目的任务C所有M个项目都是完整的

例如：

if say N = 3 and M = 2 (it means we must select M items out of 3 items in total)
         Tasks: A  B  C
       item 1 : 1  2  2
       item 2 : 3  4  1
       item 3 : 3  1  2

如果我们选择项目1和项目3，则两个项目的任务A在完成后3个单位（项目1等待项目3完成），然后两个项目的任务B在接下来的2个单位时间后完成。同样，任务C在2个单位时间后完成。因此，总时间为7（这是我们可以找到的最小可能组合）。

If we select item 1 and item 3, task A of both items gets completed after 3 units(item 1 waits for item 3 to finish), then task B of both the items gets completed after the next 2 units time. Similarly, task C gets completed after 2 units time. Hence the total time is 7(which is the minimum possible combination we can find)

我尝试过考虑针对该问题的动态编程解决方案。但是我无法得到这个问题的具体解决方案。任何人都可以通过提供有效的解决方案来帮助我。

I have tried thinking of a Dynammic programming solution to the problem. But am unable to get a concrete solution to the problem. Could anyone help me out by giving a valid solution to the problem.

PS：请不要编写代码。我只是在这里寻找逻辑。

PS: Please don't write the code. I am just looking for the logic here.

谢谢。

推荐答案

通过贪婪方法（权重计算+截止日期排序）解决方案

在这里，我希望通过贪婪的方法解决此问题它有助于。

Here is a greedy approach for the solution of this problem, I hope it helps. Good luck!

由于一项内的每个任务都需要时间T才能完成，因此我们可以将其视为最后期限。这些任务（A，B和C）。并且我们可以可视化这些截止日期，就好像它们是空档一样。

Since each task within an item takes time T to complete, we can think of these as "Deadlines" for these tasks (A, B and C) . And we can visualise these deadlines as if they were "slots" within an array/train of slots.

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

In order to visualize these deadlines consider these examples;

项目2的任务A；

0__A__1__A__2__A__3

0__A__1__A__2__A__3

项目1的任务C;

0__C__1__C__2

0__C__1__C__2

让我们考虑一下现在我们有K个插槽在我们手中0__1__2__ ... __K的范围内，该问题要求我们尽可能减少插槽的花费。

Let's consider this now; We have an K amount of "slots" within our hand 0__1__2__ ... __K and the problem asks us to spend minimum amount of slots as possible.

从您的解释中选择的另一个示例，当您选择item1时，可以更好地可视化问题并且item3我们的广告位采用了这种形式；

Another example from your explanation for better visualization of the problem, when you chose the item1 and item3 our slot took this form;

item1 + item3截止时间槽占用

item1 + item3 "deadline slot occupation"

0_A_1_A_2_A_3_B_4_B_5_C_6_C_7

0_A_1_A_2_A_3_B_4_B_5_C_6_C_7

前三个插槽被占用，因为item3的任务A比item1长3个单位。任务B只能在该更长的时间开始时开始。因此，任务A从插槽号3开始完成。

First three slots are occupied because item3's task A takes 3 units longer than item1. Task B can only start when this "longer" task A is done therefore starts from the slot number 3.

因此问题就出在这里；在我们的广告位中填满最少要使用的广告位。因此，我们将对这个问题采取一种贪婪的方法。

Therefore the problem becomes this; Fill our slot with the MINIMUM amount of slots spent. Therefore we will take a greedy approach into this problem.

• 查找单个截止期限对于我们要从N个项目中选择的M个项目

在您提供的示例中；

对于item1；

0_A_1_B_2_B_3_C_4_C_5

0_A_1_B_2_B_3_C_4_C_5

已占用5个插槽

对于item2;
占用8个插槽

For item2; 8 slots occupied

对于item3;
占用6个插槽

For item3; 6 slots occupied

对于itemX；
已占用P个插槽，依此类推....

For itemX; P slots occupied and so on....

在知道每个项目在任务时间上需要的插槽数量
我们将在N个项目任务时间内检查M个 Subtractions 作为项目的组合，以获得可能的最小编号。

After knowing the number of slots each item demands on task times we will check M number of Subtractions as combinations of items within N number of item task times to get the SMALLEST number possible.

示例；
当M = 2时可供M个项目选择；

Example; For M items to choose when M=2;

Item1-Item2 = 5;

Item1-Item2 = 5;

Item1-Item3 = 3;

Item1-Item3 = 3;

Item2-Item3 = 4;

Item2-Item3 = 4;

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

**edit; Item1 - Item2 corresponds to absolute value of subtractions within the combinations of chosen number of items; such as if M=2; |a1-a2| + |b1-b2| + |c1-c2| ...

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

Therefore for M=2 choices we take the minimum result of 3 which leads us to choosing Item1 and Item3 as solution.

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

This number will give us the minimum number of slots used. Hence, this leads us to the solution.

这篇关于从N个项目中选择M个项目，以使完成这些M个项目的任务花费的时间最少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！