协会网站建设的作用/网推怎么做最有效

C - 装箱问题 c++代码详细讲解

Sample Input

0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 0 0 0 0 

Sample Output

2 
1 

解题思路：
因为高一定，题目无需考虑体积，只需考虑面积。

6 * 6的货物只能单独装在一个6 * 6的包裹中。
5 * 5的货物只能单独装在一个6 * 6的包裹中。但还剩下11个1 * 1的空间。

4 * 4的货物只能单独装在一个6 * 6的包裹中。但还剩下5个2 * 2的空间。

3 * 3的货物就有多种不同的放法，但每4个3 * 3的货物必定放在1个6 * 6的包裹中。

2 * 2和1 * 1的货物只需要找包裹剩下的空间是否能容纳这些货物，倘若不能再拿6 * 6的包裹封装剩余的1 * 1和2 * 2的货物，直到货物全部装箱。这两种放在最后见缝插针最有效。

程序设计：

1. 我们比价容易想到的是程序用的是贪心的算法，就是把尽可能多的不同规格的货物存到同一个包裹中，这时候，我们就需要考虑6 * 6，5 * 5，4 * 4，的货物有多少件，因为他们都自成一个包裹，6 * 6的包裹中不可能放得下两个4 * 4的货物对吧？？
2. 在考虑完上面几种规格的货物后，我们接着考虑3 * 3的货物，因为4个3 * 3的货物必然放在一个6 * 6的箱子里，所以我们就考虑3 * 3的货物最多需要多少个包裹。

重点：假设现在有3 * 3的货物c个，则最少需要的包裹数为：(c + 3)/4;

3. 最后，我们就知道我们最少需要多少个包裹了，这时候就要计算下2 * 2和1 * 1的所有货物能否插入到这些包裹的缝隙里，倘若行，就插入，倘若不行，则得再增加一个6 * 6的包裹来装下他们。

AC代码：

#include "iostream"
using namespace std;
int main(){int a,b,c,d,e,f;while (true){int N = 0;// 计算需要的包裹数cin>>a>>b>>c>>d>>e>>f;if (a==0&&b==0&&c==0&&d==0&&e==0&&f==0)break;N = f+e+d+(c+3)/4;// 从6开始，计算最少需要的箱子数int y=5*d;// y:计算可存放2*2货物的空隙个数if (c%4==1) y+=5;else if (c%4==2) y+=3;else if (c%4==3) y+=1;if (b>y){// 如果2*2预留位不够再加包裹N += (b-y+8)/9;}int x = 36*N-36*f-25*e-16*d-9*c-4*b;// x计算可存放1*1箱子的个数if (a>x){N += (a-x+35)/36;}cout<<N<<endl;}
}

文章参考网址：
1.参考地址1
2.参考地址2