首页 > 试题广场 >

装箱

[编程题]装箱
  • 热度指数:1129 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1×1、2×2、3×3、4×4、5×5、6×6。这些产品通常使用一个 6×6×h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

输入描述:
输入包含多组数据。

每组数据一行,包含六个自然数,分别表示1×1至6×6这六种产品的数量。


输出描述:
对应每组输入,输出最小的包裹数。
示例1

输入

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

输出

2
1
# 假设1x1到6x6的产品各自有a,b,c,d,e,f个

# 对于6x6的产品,一个箱子最多只能装入1个,无剩余空间
# 因此,所有6x6的产品总共需要的箱子数=1x1的产品数f

# 对于5x5的产品,一个箱子最多只能装入1个,剩余空间可以装入11个1x1的产品
# 因此,所有5x5的产品总共需要的箱子数=5x5的产品数e

# 对于4x4的产品,一个箱子最多只能装入1个,剩余空间可以装入5个2x2的产品
# 因此,所有4x4的产品总共需要的箱子数=4x4的产品数d

# 对于3x3的产品,一个箱子可以装1个、2个、3个或者4个
# (1)如果装入1个3x3的产品,那么剩余空间可以装入5个2x2的产品+7个1x1的产品
# (2)如果装入2个3x3的产品,那么剩余空间可以装入3个2x2的产品+6个1x1的产品
# (3)如果装入3个3x3的产品,那么剩余空间可以装入1个2x2的产品+5个1x1的产品
# (4)如果装入4个3x3的产品,无剩余空间
# 因此,所有3x3的产品总共需要的箱子数=(3x3的产品数c+3)//4

# 对于2x2的产品,一个箱子可以装9个,无剩余空间
# 同时注意到:
# 装有4x4产品的箱子还可以装入5个2x2的产品,
# 装有3x3产品的箱子,也还可以装入若干个2x2的产品,对应关系如下:
#       装入1个3x3的产品,剩余空间还可以装入5个2x2的产品
#       装入2个3x3的产品,剩余空间还可以装入3个2x2的产品
#       装入3个3x3的产品,剩余空间还可以装入1个2x2的产品
# 本着使用最少箱子数的原则,有2x2产品的空余位置则优先填补到空余位置
# 因此,如果所有2x2产品总共需要的箱子数小于当前空余位置数,则无需为2x2的产品开辟新的箱子,否则,计算没装完的2x2的产品数,开辟新的箱子

# 至此,对于3x3,4x4、5x5和6x6的产品,总共需要的箱子数=`(c+3)//4+d+e+f`
# 对于2x2的产品,一个4x4的产品占用一个箱子,剩余位置可以装入5个2x2的产品
#               剩余3x3产品的个数与剩余3x3产品所在箱子剩余位置可以装入的2x2产品的数量对应关系为:{4:0, 1:5, 2:3, 3:1},
#               用数组表示为arr=[0,5,3,1],数组下表是剩余3x3产品数,数组元素是对应空余位置能装入的2x2的产品数
# 因此,对于2x2的产品,如果2x2产品数小于剩余空闲位置能够容纳的2x2产品数=`d*5+arr[c%4]`,那么无需额外开辟新的箱子
#                    反之,计算多出来无法装入的2x2产品数,这些多出来的2x2产品(假设有num个)总共需要的箱子数=(num+8)//9

# 最后,对于1x1的产品,将全部空间减去2x2到6x6产品所占用的空间need1num=box_num*36-(f*36+e*25+d*16+c*9+b*4),看看剩余空间能不能装入全部的1x1产品
# 如果能,那么无需开辟新的箱子,否则,多出来num=a-need1num个箱子,那么总共需要新开辟的箱子数=(num+35)//36
# 注意,在计算2x2产品需要的箱子数时,已经包含了将2x2产品装入到4x4和3x3产品所在箱子剩余空闲位置这一事实

def box(a,b,c,d,e,f):
    # 3x3到6x6的产品需要的箱子数
    box=(c+3)//4+d+e+f
    
    arr=[0,5,3,1]#4,1,2,3个3x3产品对应剩余位置能够装入的2x2产品数
    # 3x3到6x6的产品(其实就是4x4和3x3的)需要的箱子剩余未知能够容纳的2x2产品数
    need2num=d*5+arr[c%4]
    # 2x2产品需要的箱子数
    if need2num<b:
        box+=((b-need2num)+8)//9

    # 1x2到6x6的产品(其实就是5x5,4x4,3x3和2x2的)需要的箱子剩余未知能够容纳的1x1产品数
    need1num=box*36-(f*36+e*25+d*16+c*9+b*4)
    # 1x1产品需要的箱子数
    if need1num<a:
        box+=((a-need1num)+35)//36
    
    return box

while True:
    try:
        a,b,c,d,e,f=list(map(int,input().split(' ')))
        res=box(a,b,c,d,e,f)
        print(res)
    except:
        break

发表于 2022-06-30 12:58:17 回复(0)
笨办法,从装5X5的箱子开始计算分别能装入多少1X1、2X2的,等1X1和2X2的都装满了就终止,如果2X2的被多存放了(就是实际没有那么多2X2),再用1X1的去占这些2X2的份额
is_empty = [0] * 6
while True:
    try:
        parcels = list(map(int, input().split()))
        if parcels == is_empty:
            print(0)
            continue
        sealed, parcels[2] = divmod(parcels[2], 4)
        sealed += sum(parcels[3:])
        
        parcels[0] -= parcels[4] * 11
        can_pack = [0, parcels[3] * 5]
        if parcels[2] > 0:
            sealed += 1
            tmp = 9 - 2*(parcels[2] + 1)
            can_pack[1] += tmp
            can_pack[0] = 36 - parcels[2]*9 - tmp*4
        parcels[1] -= can_pack[1]
        parcels[0] -= can_pack[0]
        if parcels[1] <= 0:
            parcels[0] += parcels[1] * 4
            if parcels[0] <= 0:
                print(sealed)
                continue
        tmp = int(parcels[1]//9)
        parcels[1] = parcels[1] - tmp*9
        sealed += tmp
        if parcels[1] > 0:
            sealed += 1
            parcels[0] -= 36 - parcels[1]*4
        if parcels[0] > 0:
            tmp = parcels[0] % 36
            sealed += parcels[0]//36 if tmp == 0 else parcels[0]//36 + 1
        print(sealed)
    except:
        break


发表于 2021-08-02 17:04:11 回复(0)