首页 > 代码库 > POJ 1017 Packets-装格子 (简单贪心)

POJ 1017 Packets-装格子 (简单贪心)

http://poj.org/problem?id=1017

1.题意:

一个工厂制造的产品形状都是长方体盒子,它们的高度都是 h,长和宽都相等,一共有六个型号,分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。

这些产品通常使用一个 6*6*h 的长方体箱子包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的箱子数量BoxNum。

 

2.解题思路:

由于盒子和箱子的高均为h,因此只需考虑底面积的空间。

 

6*6的盒子,每个盒子独占一个箱子。

5*5的盒子,每个盒子放入一个箱子,该箱子的剩余空间允许放入的最大尺寸为1*1,且最多放11个。

4*4的盒子,每个盒子放入一个箱子,该箱子的剩余空间允许放入的最大尺寸为2*2。

3*3的盒子,每4个刚好独占一个箱子,不足4个3*3的,剩下空间由2*2和1*2填充。

2*2的盒子和1*1的盒子主要用于填充其他箱子的剩余空间,填充后的多余部分才开辟新箱子装填。

#include<stdio.h>
int main(){
    int n,a,b,c,d,e,f,x,y;
    int u[4]={0,5,3,1};
    while(1){
        scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
        if(a==0&&b==0&&c==0&&d==0&&e==0&&f==0)
            break;
        n=d+e+f+(c+3)/4;
        y=5*d+u[c%4];
        if(b>y)
            n+=(b-y+8)/9;
        x=36*n-36*f-25*e-16*d-9*c-4*b;
        if(a>x)
            n+=(a-x+35)/36;
        printf("%d\n",n);
    }
    return 0;
}


POJ 1017 Packets-装格子 (简单贪心)