从 N 个项目中选择 M 个项目，使得完成这 M 个项目的任务所需时间最少。

Question

从 N 个项目中选择 M 个项目，使得完成这 M 个项目的任务所需时间最少。

javaalgorithmdata-structuresdynamic-programminggreedy

3

我将尝试解决以下问题：给定N个项目，每个项目包含三个任务A、B和C。完成任务A需要TA的时间，完成任务B需要TB的时间，完成任务C需要TC的时间。现在，我们必须选择M个项目，使得完成这些M个项目的任务所需的时间最短。下面是规则：

所有选定的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，则在3个单位时间内完成两个项目的任务A(项目1等待项目3完成)，然后在接下来的2个单位时间内完成两个项目的任务B。同样，任务C在2个单位时间内完成。因此，总时间为7(这是我们可以找到的最小可能组合)。

我曾尝试过思考动态规划解决方案，但无法得出具体的解决方案。是否有人可以帮助我提供一个有效的问题解决方案。

附言：请不要编写代码。我只是在这里寻找逻辑解答。

提前感谢你的帮助。

- nishant_boro

限制条件：1 <= N <= 2000，1 <= M <= N，1 <= items[i] <= 10^9。 - nishant_boro

如何提问和回答作业问题 - 即使您不要求代码，发布您已经尝试过的内容也会有所帮助。 - Gryphon

请问您能帮我理解被接受的答案中的新减法方法吗？如果输入是[{2,2,2}, {2,2,2}, {3,3,3}, {3,3,3}], M = 2，它会如何运作？据我所知，Item1-Item2 = 0，但是Item3-Item4 = 0，那么我们该如何选择更好的一个，也就是(Item1, Item2)呢？ - גלעד ברקן

2个回答

0

使用优先队列或排序的解决方案

假设我们选择了一些M个元素，它们的最大值分别为Amax、Bmax和Cmax，则我们可以确定数组中必定存在某个元素满足A = Amax，同样对于B和C也是如此，因此我们可以说A、B、C最多有N个不同的值。因此，(Amax，Bmax，Cmax)的可能组合最多为N^3。然后，我们可以检查是否有至少M个元素在数组中满足每个组合的约束条件，并使用ans = max(ans，Amax + Bmax + Cmax)更新答案值。这种方法需要O(N^4)的时间。

但是，我们可以使用排序或优先队列来降低时间复杂度至O(N^3logN)，其中以Cmax为级别。基本上，找到所有满足Amax和Bmax约束条件的元素，并存储所有这些元素的C值，然后在Cmax的数组中找到第M小的值。

- arnold

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MrBulut · Accepted Answer

贪心方法的解决方案（重量计算+截止日期排序）

这里提供了一个贪心方法来解决这个问题，希望能对你有所帮助。祝你好运！

由于每个项中的每个任务需要时间T才能完成，我们可以把它们看作是这些任务(A, B和C)的“截止日期”。我们可以将这些截止日期想象成一个数组/列车上的“插槽”。

为了可视化这些截止日期，考虑以下例子：

第2项的任务A；

0__A__1__A__2__A__3

第1项的任务C；

0__C__1__C__2

现在让我们来考虑一下；我们手头有K个“插槽”0__1__2__...__K，问题要求我们尽可能少地使用插槽。

另一个例子用于更好地可视化这个问题，在您选择了item1和item3之后，我们的插槽会变成这样；

item1 + item3 "deadline slot occupation"

0_A_1_A_2_A_3_B_4_B_5_C_6_C_7

前三个插槽被占用，因为item3的任务A比item1需要多3个单位的时间。只有当这个“更长”的任务A完成后，任务B才能开始，因此从插槽编号3开始。

因此问题变成了这样：用最少的插槽来填充我们的插槽。因此，我们将采用贪心方法解决这个问题。

找到M个要从N个项中选择的单独的“截止日期插槽”

在您提供的示例中：

对于item1；

0_A_1_B_2_B_3_C_4_C_5

占用了5个插槽

对于item2；

占用了8个插槽

对于item3；

占用了6个插槽

对于itemX；

占用了P个插槽，依此类推....

知道每个项在任务时间上需要占用多少个插槽之后，我们将检查M个减法作为N个项任务时间内项的组合，以得到最小可能的数字。

例如；当M=2时，对于要选择的M个项；

Item1-Item2 = 5;

Item1-Item3 = 3;

Item2-Item3 = 4;

**编辑；Item1 - Item2 对应于被选定数量的项内部的减法绝对值；例如，如果M=2; |a1-a2| + |b1-b2| + |c1-c2| ...

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

这个数字将给出我们所使用的最小插槽数。因此，这将引导我们到解决方案。