问题描述

一个工厂制造的产品形状都是长方体，它们的高度都是 h，长和宽都相等，一共有六个型号，他们的长宽分别为 1*1, 2*2, 3*3, 4*4, 5*5, 6*6.  这些产品通常使用一个  6*6*h  的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

输入数据

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空

格隔开，分别为 1*1 至 6*6 这六种产品的数量。输入文件将以 6 个 0 组成的一行结尾。

输出要求

除了输入的最后一行 6 个 0 以外，输入文件里每一行对应着输出文件的一行，每一行输

出一个整数代表对应的订单所需的最小包裹数。

输入样例

0 0 4 0 0 1 

7 5 1 0 0 0 

0 0 0 0 0 0 

输出样例

2 

1 

 

问题分析：

由题意可知，可

（1）每一个6×6的产品都必须要一个箱子来装，且每个箱子刚好没有空位子；

（2）每一个5×5的产品也必须要一个箱子来装，且每一个装5×5的 箱子都有11个1×1的产品的空位子（因为剩下规格的 产品装不下）；

（3）每一个4×4的产品也必须要一个箱子来装且每一个装4×4的 箱子剩下5个2×2的产品的空位子。（ps:这里优先考虑装2×2大规格的产品，当然这里也可以剩下20个1×1的产品的空位子，这里先不考虑，如果没有2×2规格的产品，再考虑1×1的产品，后面我会统一计算1×1的空位子的个数）

（4）对于3×3的产品，由于每4个3×3的产品才能装满一个箱子，所以对于用一个箱子来装3×3的产品时，空余的位子的情况比较复杂，一共分为四种情况：

          ①3×3的产品个数a3刚好是4的倍数，这样就没有空位子

          ②3×3的产品个数a3是4的倍数还多了1个3×3的产品，这时需要箱子的数量为(a3/4)向上取整，即（a3+3）/4个箱子，且这种不满的箱子都留下了5个2×2的空位子以及7个1×1的空位子（其余的规格不适合填装）

          ③3×3的产品个数a3是4的倍数还多了2个3×3的产品，这时需要箱子的数量为(a3/4)向上取整，即（a3+3）/4个箱子，且这种不满的箱子都留下了3个2×2的空位子以及6个1×1的空位子（其余的规格不适合填装）

         ④3×3的产品个数a3是4的倍数还多了3个3×3的产品，这时需要箱子的数量为(a3/4)向上取整，即（a3+3）/4个箱子，且这种不满的箱子都留下了1个2×2的空位子以及5个1×1的空位子（其余的规格不适合填装）

（4）对于2×2的产品，每9个2×2产品才能填满一个箱子，根据以上所有情况留下的2×2的空位子数量x，与2×2的产品的数量a2进行比较，如果2×2的产品的数量多于2×2空位子个数，则根据剩下的2×2产品的数量来继续添加箱子的个数，每9个2×2产品才能填满一个箱子，这时需要再添加箱子的数量为（a2-x）/9向上取整，即（a2-x+8）/9个箱子，对于一个箱子不足9个2×2产品的，用1×1的产品来填满。如果2×2的产品的数量小于2×2空位子个数，直接将2×2的产品填入空位子，剩下的空位子全部用1×1的产品来填。

（5）对于1×1的产品，每36个1×1的产品才能装满一个箱子，根据以上所有情况留下的1×1的空位子数量y，与1×1的产品的数量a1进行比较，如果1×1的产品的数量多于1×1空位子个数，则根据剩下的1×1产品的数量来继续添加箱子的个数，每36个1×1产品才能填满一个箱子，这时需要再添加箱子的数量为(a1-y)/36向上取整，即（a1-y+35）/36 个箱子

综上可以得出最少需要箱子的个数

c语言源码：

#include<stdio.h>
#include<stdlib.h>

int main(){
 int x,y,cnt;  //x为2×2的空位子数量，y为1×1的空位子数量
 int a1,a2,a3,a4,a5,a6; //6个包裹的大小
 int c[4]={0,5,3,1};  //当有3×3的时，则2×2的空位子数量可能的个数，这是3×3到2×2的空位子数量的映射
 while(1){
	 cnt=0;
  scanf("%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5,&a6);
  if(a1==0&&a2==0&&a3==0&&a4==0&&a5==0&&a6==0)
	  break;
  cnt+=a6+a5+a4+(a3+3)/4;  //a6和a5和a4以及（a3+3）/4都分别占用一个箱子，（a3+3）/4是对a3每满4向上取整的个数
  x=5*a4+c[a3%4];   //这是计算2×2空位子的总个数，每一个a4装的箱子都有着5个2×2的空位子+每一个a3装的箱子可能存在2×2的空位子数量
  if(a2>x)   //计算a2的数量是否大于其空位子的数量
	  cnt+=(a2-x+8)/9;  //计算a2填满空位子后剩余的a2所需要的箱子的个数。（a2-x+8）/9是对a2每满9向上取整的箱子个数
  y=36*cnt-36*a6-25*a5-16*a4-9*a3-4*a2;  //计算剩余1×1空位子的个数
  if(a1>y)//计算a1的数量是否大于其空位子的数量
	  cnt+=(a1-y+35)/36;//计算a1填满空位子后剩余的a1所需要的箱子的个数.(a1-y+35)/36是对a1每满36向上取整的箱子个数
 printf("%d\n",cnt);
 }
return 0;
}