这是算法设计课上老师出的一道思考题，查了一下来源，是 POJ的1017号题，出自 Central Europe 1996

¶问题描述

某工厂的产品的形状都是长方体，长和宽都相等， 高度都是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

¶算法思路

这是一道纯模拟题，按一般思路就可以构造出通解程序。

• 由于产品和包裹的高度都是H，所以只需要考虑平面上正方形的摆放方式；
• 对于[6*6]、[5*5]、[4*4]的产品，每个包裹只能容纳一个这样的产品，所以箱子的数目至少有这类的产品个数的总和；
• 对于装有[6*6]产品的包裹，已经没有额外的空间可以装其它产品；
• 对于装有[5*5]产品的包裹，至少还可以装下11个[1*1]的产品；
• 对于装有[4*4]产品的包裹，至少还可以装下5个[2*2]的产品（或每个[2*2]的产品等价为4个[1*1]产品）；
• 一个新的包裹至少可以放得下4个[3*3]的产品，如果有剩于空间，可分为三种情况：
  • 剩3个[3*3]的产品的空间，可以放下5个[2*2]与7个[1*1]的产品；
  • 剩2个[3*3]的产品的空间，可以放下3个[2*2]与6个[1*1]的产品；
  • 剩1个[3*3]的产品的空间，可以放下1个[2*2]与5个[1*1]的产品；
• 如果还有空间，可用[1*1]的产品填充；
• 一个新的包裹至少可以放得下9个[2*2]的产品，如果有剩于空间，可用[1*1]的产品填充；
• 一个新的包裹至少可以放得下36个[1*1]的产品；
• 统计所有的箱子数。

¶实现代码

#include <stdio.h>

#define ONE		0
#define TWO		1
#define THREE	2
#define FOUR	3
#define FIVE	4
#define SIX		5

int main(void) {
	int boxes[6[ = { 0 };
	int index, flag;
	while (1) {
		// input
		for (index = flag = 0; index < 6; index++) {
			scanf("%d", &boxes[index]);
			flag += boxes[index];

		}

		if (!flag) // 0 0 0 0 0 0
			break;

		// init
		int box_num = 0, i;

		// 6*6 boxing
		box_num += boxes[SIX];
		// 5*5 boxing
		box_num += boxes[FIVE];
		// 4*4 boxing
		box_num += boxes[FOUR];

		// 1\*1 boxing in 5\*5
		for (i = 0; i < boxes[FIVE]; i++) {
			if (0 < boxes[ONE])
				boxes[ONE] -= 11;
		}

		// 1\*1 and 2\*2 boxing in 4*4
		for (i = 0; i < boxes[FOUR]; i++) {
			if (0 < boxes[TWO]) {
				boxes[TWO] -= 5;
				// instead 2\*2 of 1\*1 boxing in 4*4
				for (; boxes[TWO] < 0; boxes[TWO]++)
					if (0 < boxes[ONE])
						boxes[ONE] -= 4;
			} else
				boxes[ONE] -= 20;

		}

		// 3*3 boxing
		while (0 < boxes[THREE]) {
			boxes[THREE] -= 4;
			box_num++;
		}
		// 1\*1 and 2\*2 boxing in 3*3
		switch (boxes[THREE]) {
		case -3:
			boxes[TWO] -= 5;
			boxes[ONE] -= 7;
			break;
		case -2:
			boxes[TWO] -= 3;
			boxes[ONE] -= 6;
			break;
		case -1:
			boxes[TWO] -= 1;
			boxes[ONE] -= 5;
		}
		// instead 2\*2 of 1\*1
		if (boxes[TWO] < 0) {
			while (boxes[TWO]++)
				if (0 < boxes[ONE])
					boxes[ONE] -= 4;
		} else {
			// 2*2 boxing
			while (0 < boxes[TWO]) {
				boxes[TWO] -= 9;
				box_num++;
			}

			// 1\*1 boxing in 2\*2
			for (; boxes[TWO] < 0; boxes[TWO]++)
				if (0 < boxes[ONE])
					boxes[ONE] -= 4;
		}

		// 1*1 boxing
		while (0 < boxes[ONE]) {
			boxes[ONE] -= 36;
			box_num++;
		}

		printf("%d\\n", box_num);

	}
	return 0;
}

以上代码通过 GCC 编译，已经被 POJ Accepted :) 下载地址：GoogleCode

注意：

使用 Visual C++ 6.0 的同学，代码可能无法正常通过编译，请自行处理 :(