从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:
- 同时选中所有M个项目，即同时操作所有M个项目
- 除非所有M个项目的任务A完成，否则任何选定项目的任务B都无法启动
- 除非所有M个项目的任务B完成，否则任何选定项目的任务C都无法启动
例如:
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个插槽
对于项目3； 占用了6个插槽
对于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;
**编辑；项目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.
此数字将为我们提供所使用的最小插槽数.因此，这将我们引向解决方案.
This number will give us the minimum number of slots used. Hence, this leads us to the solution.
这篇关于从N个项目中选择M个项目，以便完成这些M个项目所需的时间最少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
