最小总容器大小 Python

Question

我正在练习一些 Amazon 面试编码练习，但我一直坚持这个练习。

简而言之，给定一个列表l和一个整数d，我必须将列表分成d个部分，使得每个部分的最大值之和最小，因为例如，l = [10,2,20,5,15,10,1], d = 3 应该 return 31 因为最佳选择是 [10,2,20,5,15],[10],[1] -> 20+10+1 = 31.

Link 问题：Problem

我考虑过将列表分成 2 部分并递归调用第一部分和 d-1，然后取第二部分的最大值（第二部分将开始有一个元素，我们将添加一个元素每次迭代到这部分）。

我这样做了，但出现“调用 Python 对象时超出最大递归深度”错误。我知道这个问题的解决方案很容易找到，但我想了解为什么这种方法不起作用。

def getmin(l, d):
    # base case, if the list has d elements each element will be a sublist
    if len(l)==d: 
        return sum(l)
    else:
        minn = float("inf")
        for i in range(1, len(l)-d+1):
            val = getmin(l[0:-i], d-1) + max(l[-i:])
            if minn > val:
                minn = val
    return minn

Answer 1

对于简单的情况，d=1，解就是列表的最大值

def getmin(l, d):
    if d == 1:
        return max(l)

当d大于1时，解决方法是return递归调用的结果中加入链表头部或尾部较小的那个

def getmin(l, d):
    if d == 1:
        return max(l)
    if l[0] < l[-1]:
        return l[0] + getmin(l[1:], d-1)
    else:
        return getmin(l[:-1], d-1) + l[-1]

Answer 2

您的列表 l 不是您所写示例的二维列表，因此您的算法似乎无法保存结果列表，该结果列表存储您为到达特定点所做的切割和输入列表直的。保留一个单独的列表并将结果累积到其中要容易得多，将 l 视为只读。更不用说，从性能的角度来看，每次递归调用都复制它是痛苦的。

在继续之前，Python 推荐 never using l as a variable name。更喜欢 L、nums 或 lst——很难区分 1、i 和 l。 post.

的其余部分我将使用 L

一个类似于你的蛮力解决方案是运行从 0 到 len(L) 的计数器并使用递归来尝试每个节点的每个可能性。在每个 i 处，我们可以将当前数字 L[i] 附加到最后一个桶，或者以 L[i] 作为第一个元素开始一个新桶。一个小的优化是只保留每个桶的最大值而不是所有元素。

现在您有了蛮力解决方案，您可以重复 cache to memoize 个工作。

from functools import cache
import random

def min_sum_of_max_elems_from_d_cuts(L, d):
    assert len(L) >= d

    @cache
    def find_best_cut(i, cuts):
        if len(cuts) == d and i == len(L):
            return sum(cuts)
        elif len(cuts) > d or i >= len(L):
            return float("inf")

        best = float("inf")

        if cuts: # try extending the current cut by L[i]
            new_cuts = cuts[:-1] + (max(cuts[-1], L[i]),)
            best = min(best, find_best_cut(i + 1, new_cuts))

        #                try making a new cut at L[i]
        return min(best, find_best_cut(i + 1, cuts + (L[i],)))

    return find_best_cut(i=0, cuts=tuple())

if __name__ == "__main__":
    tests = [
        dict(L=[10,2,20,5,15,10,1], d=3, result=31),
        dict(L=[10,2,20,5,15,10,1], d=5, result=43),
        dict(L=[5,4,2,4,3,4,5,4], d=4, result=16),
        dict(L=[22,12,1,14,17], d=2, result=39),
    ]

    for test in tests:
        assert min_sum_of_max_elems_from_d_cuts(test["L"], test["d"]) == test["result"]
    
    L = random.Random(42).choices(range(200), k=25)
    assert min_sum_of_max_elems_from_d_cuts(L, d=15) == 1056

我将把优化、自下而上的 DP 和重现留给 reader。它看起来与 LeetCode 1335 的问题相同，因此目标约束是 1 <= len(L) <= 300、0 <= L[i] <= 1000 和 1 <= d <= 10，因此它需要比这更多的火力来避免 TLE。

最小总容器大小 Python

Minimum total container size Python

python

algorithm

dynamic-programming