请问这道“装箱问题”如何思考呢？

Question

请问这道“装箱问题”如何思考呢？我看代码不是很理解，希望大家提供一下详细思路，非常感谢大家！

#include <cstdio>

int main()
{
    int n, a, b, c, d, e, f, x, y;
    //n表示需要的箱子
    //x表示1×1的空位数目
    //y表示2×2的空位数目
    int u[4] = { 0,5,3,1 }
        //表示3×3产品分别是4k,4k+1,4k+2,4k+3时

        while (scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f) != EOF)
        {
            if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0 && f == 0)
                break;
            n = f + e + d + (c + 3) / 4;
            y = 5 * d + u[c % 4];
            //长宽大于或等于3×3的产品所占的新箱子数目
            if (b > y)
                n += (b - y + 8) / 9;//多出来的2×2箱子应该占用的新箱子数
            x = 36 * n - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b
                //所有箱子剩下的1×1空格
                if (a > x)
                    n += (a - x + 35) / 36;
            printf("%d\n", n);
        }
    return 0;
}

Answer 1

书写得不够好，书上对表2-2的解释不够详细。我只能自行推测其含义。
这题的主要思路是贪心法（Greedy Method），先处理大的产品，再逐次安排较小的产品。

在表2-2中：
6x6的产品需要一个箱子，且不留下任何空间，所以后面都是0；
5x5的产品需要一个箱子，且留下11个格子，也只能用于放11个1x1的箱子；
4x4的产品需要一个箱子，且留下的空间恰好够放5个2x2的箱子。（当然也可以用来放1x1的箱子，不过先考虑放2x2的嘛。）
3x3的产品比较复杂，每4个可以放满一个箱子。我推测这里的K_3指的是3x3产品的总个数，K_3 mod 4之后的余数（0至3）可能会占用一个箱子并剩下一些空间装2x2和1x1的产品，这些信息在表2-2中都有列出。

整道题的思路是，先装6x6至4x4的产品，每件产品必须要一个箱子；再装3x3的产品，需要(K_3 + 3) / 4个箱子；再在余下的空间尽可能放2x2的产品，空间不够就新增箱子；最后在余下的空间尽可能放1x1的产品，空间不够也新增箱子。

#include <cstdio>
 
int main()
{
    int n, a, b, c, d, e, f, x, y;
    // n是需要的箱子总数，即本题的答案。
    // a至f分别是1x1至6x6的产品数量。
    // x表示1×1的空位数目。
    // y表示2×2的空位数目。
    int u[4] = { 0,5,3,1 }
    // u是一个数组。
    // u[0]=0表示3x3的产品是4k个时，最后那个箱子有空位放0个2x2的产品。
    // u[1]=5表示3x3的产品是4k+1个时，最后那个箱子有空位放5个2x2的产品。
    // u[2]=3表示3x3的产品是4k+2个时，最后那个箱子有空位放3个2x2的产品。
    // u[3]=1表示3x3的产品是4k+3个时，最后那个箱子有空位放1个2x2的产品。
 
    while (scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f) != EOF) // 循环读取数据。
    {
        if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0 && f == 0)
            break;
        n = f + e + d + (c + 3) / 4; // 这句话把6x6至3x3的所有产品均装箱了。3x3产品有c个，占用了(c + 3) / 4个箱子。
        y = 5 * d + u[c % 4]; // 其中 5 * d 就是放了4x4产品的箱子中还能装多少个2x2的产品；u[c % 4]就是放了3x3产品的最后那个箱子（其他箱子都是满的）中还能装多少个2x2的产品。
        if (b > y) // 如果2x2的产品太多，依然装不下
            n += (b - y + 8) / 9; // 多出来的2×2产品应该占用的新箱子数。（一个全新的箱子能放9个2x2产品）
        x = 36 * n - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b // 所有箱子剩下的1×1空格
        if (a > x) // 如果1x1的产品太多，依然装不下
            n += (a - x + 35) / 36; // 多出来的1x1产品应该占用的新箱子数。（一个全新的箱子能放36个1x1产品）
        printf("%d\n", n); // 输出答案。
    }
    return 0;
}