C语言OJ题——1091装箱问题

本文主要是介绍C语言OJ题——1091装箱问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

装箱问题

1.题目
2.解题思路
3.代码实现
4.细节补充说明

1.题目

题目描述
一个工厂生产的产品形状都是长方体，高度都是h，主要有1 * 1，2 * 2，3 * 3，4 * 4，5 * 5，6 * 6等6种。这些产品在邮寄时被包装在一个6 * 6 * h的长方体包裹中。由于邮费很贵，工厂希望减小每个订单的包裹数量以增加他们的利润。因此他们需要一个好的程序帮他们解决这个问题。你的任务就是设计这个程序。

输入
输入包括多组测试数据，每一行代表一个订单。每个订单里的一行包括六个整数，用空格隔开，从小到大分别为这6种产品的数量。6个0表示文件结束。

输出
针对每个订单输出一个整数，占一行，代表对应的订单所需的最小包裹数。没有多余的空行。

样例输入
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

样例输出
2
1

2.解题思路

这题需要我们从大到小来分析每种型号的产品占用多大的箱子。
（1）6 * 6：毫无疑问，6 * 6的产品每个都会占用一整个箱子，因此有多少个6 * 6的产品，必须有多少个箱子，而且没有任何空余的空间存放其他产品。
（2）5 * 5：该产品也必须自己占用一个箱子，但是会有剩余，剩余的部分为6 * 6 - 5 * 5=11，这11个空间很显然只能存放1 * 1大小的产品，因此，5 * 5的可以和1 * 1放在一起，可以放11个11的产品。
（3）4 * 4：该产品也需要自己占用一个箱子，剩余的空间既可以放2 * 2的产品，能放5个，也可以全部放1 * 1的产品，能放20个。
（4）3 * 3：该产品也需要自己占用一个箱子，但是由于是6的一半，也就是说4个3 * 3的产品正好可以装满一个整箱子，因此我们可以根据3 * 3的产品数来对4求余，如果余数为0，说明正好是4的倍数，直接除以4就是所需的箱子数，不再有剩余空间。如果余数不为0，那么则是除以4取整后再加1。这时候就会出现剩余空间，这要分三种情况来考虑，一是余数为1，也即1个箱子里只放1个3 * 3的产品，那么剩余的空间为27，最多可以放5个2 * 2的空间和7个1 * 1的空间（或者全放11则可以放27个），同样，余数为2的话，则剩余的空间为18，最多可以放3个2 * 2和6个1 * 1（或者18个1 * 1），最后一种就是余数为3，则剩余空间为9，最多只能放1个2 * 2和5个1 * 1（或者9个1 * 1）。
（5）2 * 2：该产品可以和44或33产品放一起，因此我们可以先把44和33产品剩余下来的22空位全部占满，如果不够，则需要重新占用新箱子，很显然9个2 * 2产品正好占满一个箱子，所需新箱子的数量应该对9求余，余数为0，则直接整除9即可，否则整除9后再加1。
（6）1 * 1：该产品最简单了，可以先把所有剩余的11空间占满，如果不够，则重新占用新箱子，很显然一个6 * 6的箱子可以存放36个1 * 1，因此剩余的1*1产品数对36求余，余数为0，直接整除36，否则整除36加1。
最后把这6种情况各自所需的箱子数累加起来就是题目所要的结果。

3.代码实现

#include <stdio.h>
int main()
{int p[7];//p[1] - p[6]分别表示1*1，2*2,...,6*6的个数，p[0]不用管，创建7个元素只是为了对应标记方便int pack3_2[4] = {0,5,3,1},pack3_1[4] = {0,7,6,5};//pack3_2[i]表示装i个3*3时可以装2*2的个数(i>0)//也就是混装的情形while(1){int sum = 0;scanf("%d%d%d%d%d%d",&p[1],&p[2],&p[3],&p[4],&p[5],&p[6]);if(p[1] == 0 && p[2] == 0 && p[3] == 0 && p[4] == 0 && p[5] == 0 && p[6] == 0 )break;//装6*6sum += p[6];//装5*5sum += p[5];p[1] = p[1] - 11*p[5];//装4*4sum += p[4];p[2] = p[2] - 5*p[4];//优先装2*2的，所以这里不再写p[1] = p[1] - 20*p[1] —————————— (1)//装3*3sum += (p[3] + 3) / 4;p[3] = p[3] % 4;if(p[3] > 0)//剩下3*3的货物为1个或2个或3个{p[2] = p[2] - pack3_2[p[3]];p[1] = p[1] - pack3_1[p[3]];}//开始装2*2if(p[2] < 0)//说明原有的箱子够装2*2了{p[1] = p[1] + 4*p[2];//此时把原来计划用于装2*2的用来装1*1，比如2*2的箱子只有1个,(1)式中p[2] ==//-4,说明那4个原本用于装2*2的此时要装1*1}//到这里装5*5，4*4，3*3的箱子已经完全被填满，需要额外的箱子装1*1和2*2if(p[2] > 0) //还剩下2*2的{sum += (p[2] + 8) / 9;p[2] = p[2] % 9;p[1] = p[1] - (36 - p[2]*4);//这一步容易错，我就是在这里写错！！}//1*1if(p[1] > 0){sum += (p[1] + 35) /36;}printf("%d\n",sum);}return 0;
}