装包装箱问题 （C++代码）详细解答

解题思路:

根据图片，我们可以看到，我们要做的是铺平每一个箱子，也就是一个箱子只能有一层物品，因为他们高度都一样是h

1.  6*6的一个占满一个箱子

2.  5*5的不能同时放两个5*5，所以也只好一个占一个箱子，空余的空间，我们看到只能用1*1来填补，这里面放不了2*2的呀，箱子是6*6的箱子，而且只能放一层，高度大家都一样是h,注意了，可以放11个1*1来填满

3.  4*4的也是不能放两个自己，可以看到4*4的剩下的20空间，就可以用2*2和1*1来填满了，但是剩下20刚好是5个2*2填满了，就没必要用1*1了吧？除非是2*2不够的情况下，才用1*1来填满，也就是说，2*2数量满足的情况下，不需要1*1，不够才需要1*1.

4.  3*3可以看到，放4个自己的3*3就刚好放满了对吧？可以看到，3*3可以放自己1-4个都可以，所以，需要对3*3进行特殊处理：

A. 当只有1个3*3的时候---只有一个三3*3，剩下的27空间就只能用2*2和1*1来填满了。可以看到，在一个3*3情况，我们的2*2只能最多放5个2*2。如下图所示：就可以看到只能放5个2*2和7个1*1对吧？

B.  当只有2个3*3的时候，剩下18的空间同样用2*2和11来填满，如下图所示：只能用3个2*2和6个1*1了

C.  当只有3个3*3的时候,剩下9的空间，同样2*2和1*1填满，如下图所示：只能用1个2*2和5个1*1了

D .4个3*3的时候就不需要了，刚好满

好，现在经过6*6-3*3后，我们就可以看看当目前为止可以用多少个箱子装6*6-3*3

可以看到6*6，5*5，4*4都是一个用一个箱子装，然后是3*3的，满四个装一个箱子，当3*3<=3的时候也要用一个箱子装，3*3>4,就例如5个时候，要用两个了对吧，所以我们需要对3*3进行判断需要多少个箱子

也就是3*3的箱子数 = （3*3个数+3）/4

这里解释为什么要+3，假设有3个3*3，但是也要用一个箱子装，有1*个3*3也是需要一个箱子装，有2个3*3也是需要一个箱子装，也就是说 +3 是为了让它能满足4的倍数

数学计算： （1+3）/4 = 1； （2+3）/4 = 1； （3+3）/4 = 1； （4+3）/4=1；

                    （5+3）/4=2；   （6+3）/4=2；  （7+3）/4=2；     （8+3）/4 = 2；

看完应该都可以理解了为什么+3了吧？

当然，你也可以不这样做，就判断（3*3个数%4==0）是否等于0

==0就箱子数=3*3个数/4。

！=0的时候，箱子数 = 3*3个数/4+1

好，到现在就可以确定当前要的箱子数: box = d+e+f+(c+3)/4;

好，确定完6*6-3*3的，那么就剩下了2*2和1*1怎样处理了。

先处理2*2，我们可以看到，需要用到2*2的地方，只有4*4和3*3对吧？那么我们可以这样子想，我们就计算需要填满4*4和3*3一共需要多少个2*2，

如果需要的2*2个数>=现实中有的2*2个数，就是不需要多开箱子，填完2*2后还剩下的空间用1*1来填。

box+=0;

如果需要的2*2个数<现实中有的2*2个数，就是说明，填满2*2后，还有剩下2*2，那么我们就需要为多出来的2*2来多加箱子来装了对吧？

思路了解后，那么我们就要来计算，一共需要多少个2*2的个数了吧，我们用变量need2num表示

我们上面知道了，一个4*4需要5个2*2，但是对于3*3的需要2*2个数是根据3*3的个数来确定的

剩下4个3*3，需要0个2*2和0个1*1

剩下1个3*3，需要5个2*2和7个1*1

剩下2个3*3，需要3个2*2和6个1*1

剩下3个3*3，需要1个2*2和5个1*1

我们用一个数组来存放对于3*3所需要2*2的个数           int need2[4] = { 0, 5, 3, 1 };

所以           need2num = d * 5 + need2[c % 4];

这样子就求出了需要用到的2*2个数了。

得出需要2*2个数后，就可以判断需不需要加箱子了

    if (need2num >= b){ box += 0; } //2*2的箱子刚好符合或者小于需要的，就不需要在开辟box箱子了

    else box += ((b - need2num) + 8) / 9; //这里是多出来的2*2的情况，需要加box箱子，加box箱子的数目需要看多出来几个，每多出9个就多加一个box箱子，这里的+8和上面+3的想法是一模一样的

接下来，可能就想到了，用同样的方法处理1*1对吧？但是告诉你这样子想是错误的，这样子想是根据2*2可以填满的情况下，但是当2*2不够，填不满4*4和3*3需要的2*2时候，我们就需要把剩下的所有空间用1*1来填了

，很明显这样的方法不能同样处理1*1

但是我们可以根据当前箱子的总数来判断1*1的所需，

  need1num = box * 36 - (f * 36 + e * 25 + d * 16 + c * 9 + b * 4);
  if (need1num >= a){ box += 0; }
  else box += ((a - need1num) + 35) / 36;

当前箱子数*36就是总的空间，减去6*6--2*2的所有空间，剩下的就是1*1的空间了嘛，然后根据需求数量和现实1*1的的数量判断是不是要加箱子

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<functional>
#include<map>
#include<iomanip>
using namespace std;
int main(){
                int need2[4] = { 0, 5, 3, 1 };
                int a, b, c, d, e, f;
                while (cin >> a >> b >> c >> d >> e >> f){
                                if (a + b + c + d + e + f == 0)break;
                                int need2num = 0;
                                int need1num = 0;
                                int box = 0;
                                box = f + e + d + (c + 3) / 4;//6*6至到3*3首先要用了多少个box箱子
                                need2num = d * 5 + need2[c % 4];//到目前为止填满d和c一共需要的2*2的箱子数
                                if (need2num >= b){ box += 0; } //2*2的箱子刚好符合或者小于需要的，就不需要在开辟box箱子了
                                else box += ((b - need2num) + 8) / 9; //这里是多出来的2*2的情况，需要加box箱子，加box箱子的数目需要看多出来几个，每多出9个就多加一个box箱子
                                need1num = box * 36 - (f * 36 + e * 25 + d * 16 + c * 9 + b * 4);
                                if (need1num >= a){ box += 0; }
                                else box += ((a - need1num) + 35) / 36;
                                cout << box << endl;
                }
                return 0;
}