POJ1017——装箱问题
装箱问题是…一种很常见的问题。通常描述如下，有编号为1，2，3，4，5…N的N种物品，体积分别为V1,V2….VN。将这N种物品装到容量都为S的箱子里（箱子容量也可能不同）。约定往这种箱子里装进去的物品总体积不能超过S，求最少要几个这种箱子。
问题描述：
一个工厂制造的产品形状都是长方体，它们的高度都是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
————————————————————————————————————————————————————————————————————
对于这个题目，作为一个菜鸡，我首先想到的就是贪心。。大的往里塞就行了，塞不下就用新盒子。。。但是这个是一个二维的装箱问题。。可以把它理解为一个面积为36的面积，如何用这6种面积的方块去填满。
对于长宽为1的箱子：一个大箱子可以装36个
对于长宽为2的箱子：一个大箱子可以装9个
对于长宽为3的箱子：一个大箱子可以装4个
对于长宽为4、5、6的箱子：一个大箱子可以装1个，问题就在于这剩下的面积如何摆放是最优的。有最优的就用最优的，没最优的又该咋个办。
我们注意到，长宽为4，5的箱子放进去后，剩余的空间可以用长宽为1，2两种规格的箱子来填充。一个底面积为4 * 4的箱子进去了，那么剩余的地方可以填充5个2 * 2的箱子，如果2 * 2的箱子不够可以用1 * 1的箱子来补，1 * 1和2 * 2 都没有了则需要开新大箱子或者装完了。而底面积为5 * 5的箱子更简单了，如果装了进去那么只能用11个1 * 1的箱子来填。
还剩下长宽为3的箱子，因为一个大箱子最多可以同时装4个长宽为3的箱子，如果这种箱子有5个，则需要2个箱子，9个的话需要3个箱子。得出了一个结论，长宽为3的箱子的数目除以4向上取整可以获取需要的最少大箱子数。那么最后剩下的长宽为3的箱子有可能有1，2，3个。又要分情况处理了。
剩下一个：剩下27面积，剩下二个：剩下18面积，剩下三个，剩下9面积。这些面积用底面积为1和4的箱子来填充吧！但是我们忽略了一个事实，这个地方还存在着贪心的问题，我们要尽可能的多加进去2*2的箱子，然后最后再考虑1*1的面积。用总面积 – 其他箱子的面积 = 面积为1的箱子的空间。
终于，我们的问题似乎要解决了，编码怎么办….
// // main.cpp // 1017 // // Created by MadMarical on 15/11/27. // Copyright (c) 2015年 com. All rights reserved. // #include <iostream> #include <math.h> using namespace std; int main(int argc, const char * argv[]) { int boxA,boxB,boxC,boxD,boxE,boxF;//不同底面积箱子数量 int left2x2,left1x1; int countBox;//使用大箱子数量 while(cin>>boxA>>boxB>>boxC>>boxD>>boxE>>boxF) { //结束条件if (boxA == 0 && boxB == 0 && boxC == 0 && boxD == 0 && boxE == 0 && boxF == 0) { break; } //体积为4、5、6的有一个就需要一个箱子，体积为3的需要boxC / 4个箱子 countBox = boxD + boxF + boxE + (boxC + 3) / 4; //剩余的空间我们采取贪心的策略，先放2 * 2的箱子，4 * 4的箱子还剩下boxD * 5个2 * 2的空间 left2x2 = boxD * 5; //对于3 * 3底面积的需要分情况讨论 if (boxC % 4 == 3) //3 * 3的箱子装完了还剩下3个，只留下了1个2 * 2的空间 { left2x2 += 1; } else if (boxC % 4 == 2) //这种情况下留下了3个2 * 2的空间 { left2x2 += 3; } else if (boxC % 4 == 1) //注意哦，这种情况下最多可以留下5个2 * 2的空间哈 { left2x2 += 5; } if (left2x2 < boxB) { countBox += (((boxB - left2x2) + 8) / 9); //2 * 2箱子没地方的，开新箱子。 } //解决了2 * 2的空间还剩下1 * 1的,总体积减去所有其他箱子的体积，就剩下1 * 1的空间了。 left1x1 = 36 * countBox - 36 * boxF - 25 * boxE - 16 * boxD - 9 * boxC - 4 * boxB; if (left1x1 < boxA)//空间不够，加大箱子 { countBox += (((boxA - left1x1) + 35) / 36); } cout<<countBox<<endl; } return 0; }
反思：
1.ceil不知道为啥不行。
2.仔细…是解决一切的王道…