讨论/面试考题/大佬们帮忙看一道题目。做到头秃/
大佬们帮忙看一道题目。做到头秃

题目

假设有4条小船,有一堆箱子,每个箱子的重量不一定相等,现在要把这些箱子全部装到船上,要求每条船装载后载重是一样的。

请问这些箱子能否按要求装载?

输入为箱子数组,每个元素表示个箱子的重量,输出位是否能按照要求装载这些箱子。

输入

[1,1,2,2,2]

输出

true

说明

能按照要求装载,每条船载重为2

范围

箱子数不超过15, 箱子重量最高可达10e9
展开讨论
class Solution:
    def makesquare(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 4 != 0:
            return False
        target = total//4
        nums.sort()
        return self.dfs(nums, target, 0, 0, {})
        
    def dfs(self, nums, target, tmp, res, memo):
        if not nums:
            if res == 4:
                return True
            return False

        if (tuple(nums), tmp, res) in memo:
            return memo[(tuple(nums), tmp, res)]

        for i in range(len(nums)):
            if tmp + nums[i] == target:
                if self.dfs(nums[:i] + nums[i+1:], target, 0, res + 1, memo):
                    memo[(tuple(nums), tmp, res)] = True
                    return True
            elif tmp + nums[i] < target:
                if self.dfs(nums[:i]+nums[i+1:], target, tmp + nums[i], res, memo):
                    memo[(tuple(nums), tmp, res)] = True
                    return True
            else:
                break
        memo[(tuple(nums), tmp, res)] = False
        return False

排序+深搜+备忘录即可

展开全部 7 讨论