动态规划

外卖小哥的保温箱

http://www.nowcoder.com/questionTerminal/f3826b317d094e17a04e64a402bd0866

这道题整了一晚上,最后看大佬@Albert7 代码思考人生,才想出来怎么做,现在分享一下菜鸡思路
博客链接https://blog.csdn.net/qq_28597451/article/details/104691882
昨天在牛客网上做笔试题,碰到了一道题动态规划做了一晚上都没做出来,最后看着别人的答案才勉强做出来,太菜了,今天总结一下。

动态规划思路:
1、找到状态和选择,确定当前状态和转换
2、明确dp数组/或函数的定义,即dp数组保存了啥信息(dp数组一般是一维或二维)
3、寻找状态之间的关系,当前状态如何根据上一状态和一些已知信息得到(状态转换方程)

下面是解题思路

从题目可以了解到,我们需要做的是:
1、找出需要的最少的k个保温箱,使得这个k个保温箱可以装下所有的货物;
2、确定转移货物的最少时间,所以所找到的k个保温箱中所包含的货物尽可能多,则需要转移货物就越少,时间越短;

输入代码:

import sys
inp = []
while True:
    line = sys.stdin.readline().strip()
    if line == '':
        break
    line = (line.split(' '))
    inp.append([int(line[i]) for i in range(len(line))])
n = inp[0][0]
food = inp[1]
capacity = inp[2]

上面的输入莫名奇妙就爆bug了,通过不了,大概可能是原来是牛客网的输入可能混杂了空行或者为空,所以输入就出错误了,以后注意点。下面是正确(可以通过的)读取输入代码

import sys
n = int(input().strip())
lines = sys.stdin.readlines()
if len(lines) == 1:
    temp = list(map(int, lines[0].strip().split()))
    food = temp[:n]
    capacity = temp[n:]
else:
    food = list(map(int, lines[0].strip().split()))
    capacity = list(map(int, lines[1].strip().split()))
max_food = sum(food)
max_capacity = sum(capacity)

1、定义一个dp[capacity][2]数组,dp[i] = [k,food] 保存总容量为i的保温箱最少可以由k个保温箱组成,而且保温箱原来的总货物为food,应该是最大的;并初始化k的值为最大值(保温箱的数目)然后一步一步减小
2、转换方程:因为我们要保证使用的保温箱是最少的,对于第k个保温箱,当前最大容量为i,它是由容量max(i-capacity[k-1], 0)来决定的,

for k in range(1, n+1): # 对于每一个保温箱
    for i in range(max_capacity, 0, -1): # 对于当前容量最大的,从最大容量倒序
        count = dp[max(i - capacity[k-1], 0)][0]
        weight = dp[max(i - capacity[k-1], 0)][1]
        if dp[i][0] < count+1:  # 保证当前所需要的保温箱最少
            continue
        elif dp[i][0] > count+1:   # 比当前所需要的保温箱少,更新当前所选择保温箱数,货物数为之前加上当前保温箱的货物,不用比较大小,因为所需保温箱数比之前少,优先级更高
            dp[i][0] = count + 1
            dp[i][1] = weight + food[k-1]
        else: # 两者相等,取最大值
            dp[i][1] = max(weight + food[k - 1], dp[i][1])

3、寻找最优值,找到从大于等于当前货物数的容量区间[max_food, max_capacity]中,从需要箱子最少中找出货物最多的

min_step = 0
min_bin = n
for i in range(max_food, max_capacity+1):
    if dp[i][0] < min_bin:
        min_bin = dp[i][0]
        min_step = dp[i][1]
    elif dp[i][0] == min_bin:
        min_step = max(dp[i][0], min_step)
min_step = max_food - min_step

总的代码

import sys
n = int(input().strip())
lines = sys.stdin.readlines()
if len(lines) == 1:
    temp = list(map(int, lines[0].strip().split()))
    food = temp[:n]
    capacity = temp[n:]
else:
    food = list(map(int, lines[0].strip().split()))
    capacity = list(map(int, lines[1].strip().split()))

max_food = sum(food)
max_capacity = sum(capacity)
dp = [[len(food), 0] for _ in range(max_capacity+1)]
dp[0] = [0, 0]

for k in range(1, n+1):
    for i in range(max_capacity, 0, -1):
        count = dp[max(i - capacity[k-1], 0)][0]
        weight = dp[max(i - capacity[k-1], 0)][1]
        if dp[i][0] < count+1:
            continue
        elif dp[i][0] > count+1:
            dp[i][0] = count + 1
            dp[i][1] = weight + food[k-1]
        else:
            dp[i][1] = max(weight + food[k - 1], dp[i][1])
print(dp[:][:])

min_step = 0
min_bin = n
for i in range(max_food, max_capacity+1):
    if dp[i][0] < min_bin:
        min_bin = dp[i][0]
        min_step = dp[i][1]
    elif dp[i][0] == min_bin:
        min_step = max(dp[i][0], min_step)
min_step = max_food - min_step
# print(max_food, min_step)
print(str(min_bin) + ' ' + str(min_step))
全部评论
为什么要从最大容量(sum(b))倒序而不是从总货物数(sum(a))倒序呢
点赞 回复 分享
发布于 2020-03-12 00:33
就应该从总货物倒序,我觉得。这样复杂度还小些
点赞 回复 分享
发布于 2020-03-27 11:27

相关推荐

gcniz:一天写两千行你闹呢
点赞 评论 收藏
分享
8 1 评论
分享
牛客网
牛客企业服务