首页 > 试题广场 >

包裹运输

[编程题]包裹运输

热度指数：1560 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 16M，其他语言32M
算法知识视频讲解

工厂生产的产品包装在相同高度h，尺寸为1 * 1,2 * 2，3 * 3，4 * 4，5 * 5，6 * 6的方形包装中。这些产品始终以与产品高度相同的尺寸为6 * 6的包裹交付给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

输入描述:

输入文件包括几行，每一行代表一个订单。每个订单里的一行包括六个整数，中间用空格隔开，分别为 1*1 至 6*6 这六种产品的数量。输入文件将以 6 个 0 组成的一行结尾。

输出描述:

除了输入的最后一行 6 个 0 以外，输入文件里每一行对应着输出文件的一行，每一行输出一个整数代表对应的订单所需的最小包裹数。

示例1

输入

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

输出

2
1

算法知识视频讲解

Python

白色纯度

写了一百行的，你是认真的吗？这要是面试题目，时间不仅不够，面试官看到一大堆的if-else，估计看的心都没有了。这题得亏是面积的贪心排列，如果是体积的话，难度会更高。

本题思路如下：

1. 对于6*6 的直接统计数目

2. 对于5*5 的统计数目，并从1*1的包裹中选出9个来凑，如果不够，那就直接将1*1的用完了。

对应代码：

num[0] = max(0,num[0]-9*num[-2])

3. 对于 4*4 的，有些复杂。先统计数目，再拿 2*2 的凑，如果出现凑不够的情况，就在从 1*1 里面选。对应代码：

num[0] = max(0,num[0]-4*(5*num[3]-num[1]))

4. 只剩下3*3,2*2和1*1的包裹了，此时不必讨论，直接算余下的包裹总面积，除以 6*6 即可。向上取整就行。

import sys
import math
def solve(num):
    res =sum(num[-3:])
    num[0] = max(0,num[0]-9*num[-2])
    if num[1]<5*num[3]:
        num[0] = max(0,num[0]-4*(5*num[3]-num[1]))
        num[1]=0
    else:
        num[1] -= 5*num[3]
    k = num[0]+4*num[1]+9*num[2]
    res += int(math.ceil(k/36.0))
    return res
if __name__=='__main__':
    for line in sys.stdin.readlines():
        temp = list(map(int,line.split()))
        if temp == [0]*len(temp):
            break
        print(solve(temp))

发表于 2019-09-10 14:23:09 回复(0)

Python

兰偷荀令香

保存每个箱子的剩余容量和可放的最大尺寸

test_lst = []
while True:
test = list(map(int, input().strip().split()))
if sum(test) == 0:
break
test_lst.append(test)
for test in test_lst:
pack_num = test[::-1] # 6 5 4 3 2 1
largest_pack = 6
last_num = 36
pack_lst = [] # [剩余格位，剩余可放最大边长]
while sum(pack_num) != 0:
for i in range(len(pack_num)): # 打包每一个箱子
while pack_num[i] != 0: # 当前规格的箱子还有剩余需要打包
temp_pack_lst = pack_lst[:]
finish_flag = 0
for j in range(len(pack_lst)):
if pack_lst[j][0] >= (6 - i) * (6 - i) and pack_lst[j][1] >= (6 - i):
temp_pack_lst[j][0] -= (6 - i) * (6 - i)
temp_pack_lst[j][1] = i
finish_flag = 1
break
if finish_flag == 0:
temp_pack_lst.append([6 * 6 - (6 - i) * (6 - i), i])
pack_num[i] -= 1
pack_lst = temp_pack_lst[:]
print(len(pack_lst))

发表于 2019-04-04 09:51:26 回复(0)

Python

小小cx猿

#从大箱子开始装，已经AC所有样例
while(True):

n1, n2, n3, n4, n5, n6 = map(int, input().split())
if(n1==0 and n2==0 and n3==0 and n4==0 and n5==0 and n6==0):
break

ans = 0
ans += n6
ans += n5
ans += n4
ans += n3 // 4

n1 = n1 - 11 * n5

n1 = n1 - max(0, (n4 * 20 - n2 * 4))
n2 = n2 - n4 * 5

temp = n3 % 4
if(temp != 0):
ans += 1
if(temp == 1):
if(n2>0):
if(n2 <= 5):
n1 = n1 - (27 - n2 * 4)
else:
n1 = n1 - (27 - 5 * 4)
n2 = n2 - 5
else:
n1 = n1 - 27

if(temp == 2):
if(n2 > 0):
if(n2 <= 3):
n1 = n1 - (18 - n2 * 4)
else:
n1 = n1 - max(0, 18 - 3 * 4)
n2 = n2 - 3
else:
n1 = n1 - 18
if(temp == 3):
if(n2 > 0):
n1 = n1 - (9 - 1 * 4)
n2 = n2 - 1
else:
n1 = n1 - 9

if(n2 > 0):
ans += n2 // 9
if(n2 % 9 != 0):
ans += 1
n1 = n1 - (36 - (n2 % 9) * 4)
if(n1 > 0):
ans += n1 // 36
if(n1 % 36 != 0):
ans += 1
print(ans)

发表于 2019-03-27 22:12:45 回复(0)