集装箱问题 (POJ 1017)

这是算法设计课上老师出的一道思考题,查了一下来源,是 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 的同学,代码可能无法正常通过编译,请自行处理 :(