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

题目

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

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

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

输入

[1,1,2,2,2]

输出

true

说明

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

范围

箱子数不超过15, 箱子重量最高可达10e9
展开讨论
共 7 个讨论

箱子重量可以为0吗?

箱子总数/4==每条船装的重量(平均),然后依次遍历,如果小于平均,就深搜,如果大于平均,绝对false,仅供参考

你好,我刚刚思考了一下,本来是想用DP的,但是发现暴力贪心好像也可以,这是我的算法,可能存在问题和不足,我们可以多交流,可能看起来有点复杂,不过大多是判断失败,早点返回,避免不必要的运算。

int a[10];   
bool b[10];   //全局默认初始化0,表示每个箱子的状态,0未装,1装
bool pd()
{
	int n=5,i=0,j=0,sum=0;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];          //求和
	}  
	if(sum%4!=0) return false;   //不能平均整除,返回false
	int prv=sum/4;      //求均值,即每条船的上限
	
	sort(a,a+n);   //懒,就用默认从小到大排序了
	
	for(i=n-1;i>=0;i--)
	if(a[i]>prv) return false;    //存在箱子高于上限直接返回false
	
	for(i=0;i<4;i++)
	{
		sum=prv;                //  判断四次,保证每只船装完
		for(j=n-1;j>=0;j--)
		{
			if(!b[j]&&sum-a[j]>=0) {
				sum-=a[j];
				b[j]=true;          //箱子装上就置为true
			}
		}
        if(sum!=0) return false;   //如果有船装不满,也直接返回false;
	}
	
	for(i=0;i<n;i++)
	if(!b[i]) return false;    //确保所有箱子装上
	
	return true;            
}

抛砖引玉一下,只会状压 dp 后再处理,等大佬更优的解法
dp[i][j] 表示前 i 个箱子中 j 对应的箱子的总重量, 若 jk 位为 1 ,则第 k 个箱子包含在内(实际写出来可以用一维数组即可)
可以在 O(n * (2 ^ n)) 内求出所有情况,然后找到重量等于所有箱子总重量的 1/4 的结果(这样的情况应该不多)
然后 搜索 或者 再次 dp

  • 搜索:对刚刚的结果进行搜索,找 4 个能在一起能恰好用完所有箱子的情况,找到则返回 true ,否则返回 false
  • DP 看起来很简单,就不说了

题目是否可以转为 求是否存在4个和相等的子数组?

直接看leetcode473 火柴拼正方形就完事了

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

排序+深搜+备忘录即可