原題：
A factory produces products packed in square packets of the same height h and of the sizes , , , , , . These products are always delivered to customers in the square parcels of the same height h as the products have and of the size . Because of the expenses it is the interest of the factory as well as of the customer to minimize the number of parcels necessary to deliver the ordered products from the factory to the customer. A good program solving the problem of finding the minimal number of parcels necessary to deliver the given products according to an order would save a lot of money. You are asked to make such a program.
Input
The input file consists of several lines specifying orders. Each line specifies one order. Orders are described by six integers separated by one space representing successively the number of packets of individual size from the smallest size to the biggest size . The end of the input file is indicated by the line containing six zeros.
Output
The output file contains one line for each line in the input file. This line contains the minimal number of parcels into which the order from the corresponding line of the input file can be packed. There is no line in the output file corresponding to the last ``null'' line of the input file.
Sample Input
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
Sample Output
2
1
題目大意：
有1*1，2*2，3*3，4*4，5*5，6*6大小的盒子，要把它們裝到6*6的盒子裡，它們的高度都是相同的。求用最少的6*6盒子把所有尺寸的盒子都裝起來。
分析與總結：
這一題是我在Volume 4. Algorithm Design這個專題中最後才做的一題，主要是因為沒有思路。最好還是參考了別人的思路。
6*6的盒子中可以由各種尺寸的盒子來填滿。可以有以下這些情況：
1個6*6
1個5*5+11個1*1
1個4*4+5個2*2（有空隙時優先放置2*2，如果沒放完2*2的，剩下的就放置1*1）
放置3*3時，組合情況比較復雜。 沒有放完3*3時，剩下的空隙也是優先盡可能多地放置2*2
當放置1個3*3時，還可以放置7個1*1和5個2*2
當放置2個3*3時，還可以放置6個1*1和3個2*2
當放置3個3*3時，還可以放置5個1*1和1個2*2
因為一個4*4，5*5，6*6只能放置在一個盒子裡，所以有多少個這些，就需要多少個盒子來裝。
然後因為3*3的可以和1*1和2*2的組合放置，所以也可以確定裝完3*3需要的盒子。
那麼在計算時，首先就可以確定放完3*3，4*4，5*5，6*6的盒子個數，假設是t個盒子。
然後這t個盒子中會有空隙，再優先把2*2的放置到t個盒子中的空隙中。如果這些空隙不能放完2*2的，那麼就需要再增加盒子知道放完為止。最後在考慮放置1*1。
代碼：
[cpp]
/*
* UVa: 311 - Packets
* Time: 0.008s
* Author: D_Doubel
*
*/
#include<iostream>
#include<cstdio>
using namespace std;
int arr[7];
// 放置3*3的在6*6中的組合情況,優先放置更多的2*2
// 當放置1個3*3時，還可以放置7個1*1和5個2*2
// 當放置2個3*3時，還可以放置6個1*1和3個2*2
// 當放置3個3*3時，還可以放置5個1*1和1個2*2
int three[4][2]= {{0,0},{7,5},{6,3},{5,1}};
int main(){
while(~scanf("%d%d%d%d%d%d",&arr[1],&arr[2],&arr[3],&arr[4],&arr[5],&arr[6])){
if(!arr[1]&&!arr[2]&&!arr[3]&&!arr[4]&&!arr[5]&&!arr[6])break;
int ans=(arr[3]+3)/4+arr[4]+arr[5]+arr[6]; // 3*3,4*4,5*5,6*6一起用了幾個
arr[1] -= arr[5]*11; //6*6的可以放置一個5*5和11個1*1,所以直接優先把1*1和5*5放在一個盒子裡
int left_for_2=three[arr[3]%4][1]+arr[4]*5;//已用的盒子中的空隙中共還可以放置多少個2*2
if(arr[2]<=left_for_2){ // 當已用盒子中的空隙可以放置完2*2盒子時
arr[1] -= three[arr[3]%4][0]; // 在空隙中與2*2組合的可以放置的1*1個數
arr[2] -= left_for_2;
arr[1] += arr[2]*4; // 如果2*2是負數，那說明負數的絕對值是空隙，可以用來放置1*1
if(arr[1]>0) // 如果1*1還有，那麼要增加盒子
ans += (arr[1]+35)/36;
}
else{ // 不能放置完2*2
arr[1] -= three[arr[3]%4][0]; //之前和2*2組合一起填滿盒子的1*1
arr[2] -= left_for_2;
ans += (arr[2]+8)/9; // 再增加盒子直到能放完2*2
arr[1] -= (9-arr[2]%9)*4; // 增加的盒子中可能不能占滿2*2，還有空位可以放置1*1
if(arr[1]>0)
ans += (arr[1]+35)/36;
}
printf("%d\n", ans);
}
return 0;
}
