1868装包装箱问题 入门贪心算法(注释很详细)

解题思路:注意到1*1产品的特殊性:不用考虑当前箱内产品的摆放形状,只要有空间就可以见缝插针.

又考虑到面积大的产品不是那么灵活,应该要先装入箱内,然后再填充面积小的产品,进而得出贪心规则

如代码第一行所示.

注意事项:用ceil函数要记得类型转换,不然会出错.

参考代码:看上去会有点长,但很多都是注释和空行.

//贪心规则:优先装大型号的产品进入箱子,空余的空间优先塞型号大的产品

#include<bits/stdc++.h>

using namespace std;

int flag = 1;
//用于输入控制

int a[7];
//产品

int i;

int cnt;

int surplus;
//箱子的剩余空间量

int left2;
//left space for 2*2

int main()
{
	while(flag)
	{
		
		flag = 0;
		cnt = 0;
		//每轮重置循环判断变量flag和箱子总数cnt
		
		for(i = 1; i <=6; i++)
		{
			scanf("%d",&a[i]);
			
			if(a[i] != 0)
			{
				flag = 1;
			}
		}
		
		if(flag == 0)
		{
			break;
		}

		/*注意到,6*6 5*5 4*4三种型号的共同特征:每个箱子只能装一个,装两个就会超出长宽限制
		所以这三个型号的摆放规则也很简单*/
		
		//以下处理6*6型号
		if(a[6] != 0)
		{
			cnt += a[6];
			a[6] = 0;
		}//6*6已经装完
	
		//以下处理5*5型号
		//5*5型号的剩余空间可以塞1*1型号
		while(a[5] != 0)
		{
			surplus = 11;
			a[5]--;
			cnt++;
			
			while(a[1] != 0 && surplus > 0)
			{
				a[1]--;
				surplus--;
			}
		}//5*5已经装完
		
		//以下处理4*4型号
		//4*4型号的剩余空间可以塞2*2和1*1型号
		while(a[4] != 0)
		{
			surplus = 20;
			a[4]--;
			cnt++;
			
			while(a[2] != 0 && surplus > 0)
			{
				a[2]--;
				surplus -= 4;
			}//先塞2*2,通过画图可知可以刚好塞5个,所以不需要特殊处理,按面积算即可
			
			while(a[1] != 0 && surplus > 0)
			{
				a[1]--;
				surplus--;
			}//塞完2*2再塞1*1
		}//4*4已经装完
			
		/*3*3 2*2 1*1型号的共同特征:可以与同型号的产品放在一起*/
			
		//以下处理3*3型号
		//3*3优先与另外3个3*3放一起,然后余下个别放一起并且塞2*2和1*1
		if(a[3] != 0)
		{
			cnt += ceil(a[3]/4.0);
			
			a[3] = a[3] % 4;

			/*以下该段代码用画图判断,
			意为:当装a[3]个3*3的产品时,剩余的空间最多可以装多少2*2的产品*/
			if(a[3] == 3)
			{
				left2 = 1;
			}
			else if(a[3] == 2)
			{
				left2 = 3;
			}
			else if(a[3] == 1)
			{
				left2 = 5;
			}

			if(a[3] != 0)
			{
				surplus = 36 - 9*a[3];

				while(a[2] != 0 && left2 > 0)
				{
					a[2]--;
					left2--;
					surplus -= 4;
				}
				while(a[1] != 0 && surplus > 0)
				{
					a[1]--;
					surplus--;
				}
			}
		}//3*3已经放完了
		
		//以下处理2*2型号
		//2*2优先与另外8个2*2放一起,然后余下个别放一起并且塞1*1
		if(a[2] != 0)
		{
			cnt += ceil(a[2]/9.0);
			
			a[2] = a[2] % 9;
		
			surplus = 36 - 4*a[2];
			
			while(a[1] != 0 && surplus > 0)
			{
				a[1]--;
				surplus--;
			}
		}//2*2已经装完了
		
		
		//最后处理1*1
		if(a[1] != 0)
		{
			cnt += ceil(a[1]/36.0);
		}

		cout << cnt << endl;
	}
	
	return 0;
}

    再多说一点,对于5*5,4*4型号的产品,其实也可以加一个if语句优化一下提升性能,不过对于这个题是没有必要了