0

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

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

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

4

1 回答 1

1

您可以使用尾递归辅助函数：

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;

辅助函数获取源列表和正在构建的列表以及它们的总和，并将源列表的头部附加到适当的列表上，调整适当的总和，并在列表的尾部递归调用自身列表/总和。这种构建列表的方法将它们向后构造（在定义尾递归列表构造函数时并不罕见），因此没有任何剩余可处理的基本情况将它们反转。主函数简单地调用具有正确初始化列表/总和的辅助函数。

于 2017-02-01T05:47:05.187 回答