贪心算法求最优合并问题

最优合并问题可以使用贪心算法来解决。假设有n个文件，每个文件的长度为l1,l2,...,ln。现在需要将这些文件合并成一个文件，每次只能将两个文件合并，合并两个文件的代价为这两个文件的长度之和。

贪心算法的思想是每次选择长度最小的两个文件进行合并，直到所有文件都合并成一个文件为止。具体实现步骤如下：

1.将文件长度按照从小到大排序。
2.选择长度最小的两个文件进行合并，合并后的代价为这两个文件的长度之和。
3.将合并后的文件长度加入到文件长度列表中。
4.重复步骤2和3，直到所有文件都合并成一个文件为止。

代码实现如下：

def merge_files(lengths):
    n = len(lengths)
    lengths.sort() # 将文件长度按照从小到大排序
    cost = 0 # 合并代价
    while n > 1:
        min1 = lengths.pop(0) # 选择长度最小的两个文件进行合并
        min2 = lengths.pop(0)
        merge_length = min1 + min2 # 合并后的长度
        cost += merge_length # 更新合并代价
        lengths.append(merge_length) # 将合并后的文件长度加入到文件长度列表中
        n -= 1
    return cost

例如，有四个文件长度分别为[1, 2, 3, 4]，按照上述算法，先将文件长度排序为[1, 2, 3, 4]，然后选择长度最小的1和2进行合并，合并后的长度为3，代价为3，更新文件长度列表为[3, 3, 4]，再选择长度最小的3和3进行合并，合并后的长度为6，代价为6，更新文件长度列表为[4, 6]，最后选择长度最小的4和6进行合并，合并后的长度为10，代价为10，所有文件合并完成，合并代价为3+6+10=19。

贪心算法的时间复杂度为O(nlogn)，其中n为文件的个数，主要消耗时间的操作是排序操作。