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

题目

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

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

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

输入

[1,1,2,2,2]

输出

true

说明

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

范围

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

你好,我刚刚思考了一下,本来是想用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;            
}
展开全部 7 讨论