如何在SML中实现LPT（Longest Processing Time）调度算法功能

Question

假设我们有一个列表，其中包含一些任务的处理时间，例如 [13,8,7,6,4,2,2,1]。我们想通过LPT Scheduling将这个列表分成两个列表Algorithm.here是算法过程：

对于给定的降序排序列表，首先我们将最大的元素（排序列表中的第一个元素）放入 list1，然后将第二个元素放入 list2。然后我们将下一个元素插入到两个列表之一中，元素总和较小。我们做这个工作，直到初始列表中的所有元素都被分成两个列表。

例如对于上述列表，两个列表将是 [13,6,2,1],[8,7,4,2]（我们看到元素 7 已插入第二个列表，因为 ListSum( [13]>ListSum([8]) 然后因为 ListSum([13])

Answer 1

您可以使用 tail-recursive 辅助函数：

fun lpt xs = let 
    fun lpt' ([],l1,l2,s1,s2) = (rev l1, rev l2)
    |   lpt' (x::xs,l1,l2,s1,s2) = 
            if s1 <= s2 then lpt' (xs,x::l1,l2,s1+x,s2)
            else lpt' (xs,l1,x::l2,s1,s2+x)
    in
        lpt' (xs,[],[],0,0)
    end;

辅助函数获取源列表和正在构建的列表，连同它们的总和，并将源列表的头部附加到适当的列表上，调整适当的总和，并在列表的尾部递归调用自身调整后的列表 lists/sums。这种构建列表的方法向后构造它们（在定义 tail-recursive 列表构造函数时并不少见），因此没有任何东西需要处理的基本情况会反转它们。主函数只是调用正确初始化的辅助函数 lists/sums.

如何在SML中实现LPT（Longest Processing Time）调度算法功能

How to Implement LPT (Longest Processing Time) Scheduling Algorithm function in SML

sml

smlnj

ssml

sysml