动态规划

这道题整了一晚上，最后看大佬@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))