假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数n和k，以及完成任务i 需要的时间为ti ，i=1~n。计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。

这是一个经典的作业调度问题，可以使用贪心算法来解决。

具体步骤如下：

1. 将任务按照完成时间从小到大排序。

2. 初始化k个机器的完成时间为0。

3. 对于每个任务，将其分配给完成时间最早的机器，并更新该机器的完成时间。

4. 重复步骤3，直到所有任务都被分配完毕。

5. 最终完成全部任务的时间即为k个机器中完成时间最大的值。

这个算法的时间复杂度为O(nlogn)，其中n为任务的数量。

相关问题

假设有n(n<=20)个任务由k(k<=20)个可并行工作的机器完成。完成任务i需要的时间为t

假设有n个任务需要由k台可并行工作的机器来完成。每个任务完成所需的时间分别为t1, t2，…， tn。我们需要找到一个最优的分配方案，使得所有任务能够在最短的时间内完成。

首先，我们可以将任务分配给不同的机器，以减少总体完成时间。可以考虑使用贪心算法来解决这个问题。具体的分配方法可以是将任务按照所需的时间从长到短排序，然后依次分配给空闲的机器。

其次，我们还可以考虑使用动态规划来解决这个问题。具体的方法可以是用一个二维数组dp[i][j]来表示前i个任务分配给j台机器所需要的最短时间。然后使用状态转移方程来更新dp数组，最终找到最优的分配方案。

除此之外，我们还可以考虑使用回溯算法来解决这个问题。具体的方法可以是遍历所有可能的分配方案，然后找到最短的完成时间。

总的来说，解决这个问题的方法有很多种，可以根据具体的情况选择合适的算法来解决。而算法的选择也取决于任务数量n和机器数量k的大小，以及每个任务完成所需的时间t。希望能够找到一个最优的分配方案，使得所有任务能够在最短的时间内完成。

用C语言实现，假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数n和k，以及完成任务i 需要的时间为ti ，i=1~n。计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。 输入格式: 输入数据的第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。 输出格式: 将计算出的完成全部任务的最早时间输出到屏幕。 输入样例: 在这里给出一组输入。例如： 7 3 2 14 4 16 6 5 3 输出样例: 在这里给出相应的输出。例如： 17

这是一道经典的任务调度问题，可以使用贪心算法进行求解。具体做法是，将任务按照完成时间从大到小排序，然后依次将任务分配给当前完成时间最早的机器。具体实现步骤如下：

1. 读入 n 和 k 以及每个任务的完成时间 t[i]。

2. 对任务按照完成时间从大到小排序。

3. 初始化每个机器的完成时间为 0。

4. 依次将任务分配给当前完成时间最早的机器，即将任务分配给完成时间最早的机器，更新该机器的完成时间。

5. 输出所有机器中完成时间最晚的时间，即为最优调度时间。

C语言代码实现如下：