装包装箱问题 （C语言代码）

解题思路:贪心算法。

  （1） 6*6的产品每个会占用一个完整的箱子，并且没有剩余空间

  （2） 5*5的产品每个占用一个新的箱子，并且留下 11 个可以盛放 1*1 的产品的剩余空间

  （3） 4*4的产品每个占用一个新的箱子，并且留下 5  个可以盛放 2*2 的产品的剩余空间

  （4） 3*3的产品情况比较复杂，首先3*3 的产品不能放在原来装有 5*5 或者 4*4 的箱子中，那么必须为3*3 的产品另开若干个新的箱子，新开的箱子数目等于 3*3 的产品的数目除以4向上取整（可以使用ceil函数），同时需要讨论为 3*3 的产品新开箱子时，剩余的空间可以盛放多少 2*2 和 1*1 的产品：

     ① 3*3 的产品的数目恰好是4的倍数，此时还剩0个2*2的空位；

     ② 3*3 的产品数目是 4 的倍数加1， 此时还剩5个2*2的空位和7个1*1的空位；

     ③ 3*3 的产品数目是 4 的倍数加2， 此时还剩3个2*2的空位和6个1*1的空位；

     ④ 3*3 的产品数目是 4 的倍数加3， 此时还剩1个2*2的空位和5个1*1的空位；

  （5）处理完3*3的产品，就可以比较一下剩余的2*2的空位和2*2产品的数目，如果产品数目多，就将 2*2 的空位全部填满，再为2*2 的产品打开新箱子；

  （6）比较一下剩余空间与 1*1 的产品数目，如果空位多，将1*1的产品全部填入空位即可；否则，先将1*1的空位填满，然后再为 1*1 的产品打开新的箱子。

注意事项:使用ceil函数可以实现向上取整。double ceil(double x); 功 能： 返回大于或者等于指定表达式的最小整数。注意返回的是一个浮点数哦。

参考代码:

#include <stdio.h>
#include <math.h>
int main()
{
	int box[7]={0};
	int i,sum,totalbox,space2_num,space1_num; //totalbox: 需要的箱子数目，space2_num:2*2 的空位数目
                            // space1_num: 1*1 的空位数目。
	int space2[4]={0,5,3,1}; //数组space2表示 3*3 的产品数目分别是 4的倍数，4 的倍数+1, 4 的倍数+2,    
    //4的倍数+3时为3*3的产品打开的新箱子中剩余的 2*2的空位的个数 
	while(1)
	{
		sum=0;
		for(i=1;i<=6;i++)
		{
			scanf("%d",&box[i]);  //输入 1*1 至 6*6 这六种产品的数量分别保存在box[1]到 box[6]中 
			sum=sum+box[i];	
		}			
		if(sum==0) break;  
		totalbox=box[6]+box[5]+box[4]+ceil( box[3] / 4.0 );  //较大的产品只能自己开箱
		space2_num=box[4]*5+space2[ box[3]%4 ];  //每一个4*4的箱子装过后还可以再装5个2*2的箱子 
                //还有3*3的箱子如果没填满6*6的箱子的话，也可以用来装2*2的箱子 
		if(box[2]>space2_num)
			totalbox+=ceil( (box[2]-space2_num) / 9.0 );
		space1_num=totalbox*36-(box[6]*36+box[5]*25+box[4]*16+box[3]*9+box[2]*4);
		//space1_num存放多出来的面积即1*1的空位数目
		if(box[1]>space1_num)  //空间不够则新开箱
			totalbox+=ceil( (box[1]-space1_num) / 36.0 );  //向上取整
		printf("%d\n",totalbox);			
	}	
	return 0;
}