华为机考入门python3--（16）牛客16-购物单最大满意度

本文主要是介绍华为机考入门python3--（16）牛客16-购物单最大满意度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分类：动态规划，组合，最大值，装箱问题

知识点：

1. 生成递减数  100, 90, 80, ..., 0   range(100, -1, -10)

2. 访问列表的下标key    for key, value in enumerate(my_list):

3. 动态规划-捆绑装箱问题

 a. 把有捆绑约束的物体进行组合，形成唯一的个体

b. 确定动态规划表的含义，即dp[i]表示什么

c. 判断一个个体能否放入    if j - w[k] >= 0:

d.如果能放入，判断dp[i]是否需要更新    dp[j] = max(dp[j], dp[j - w[k]] + v[k])

题目来自【牛客】

买附件则一定要买对应的主件

# N 表示总钱数， m 为可购买的物品的个数
N, m = map(int, input().split())
main_parts, accessories = {}, {}
for i in range(1, m + 1):# v 表示该物品的价格， p 表示该物品的重要度， # q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号v, p, q = map(int, input().split())# 主件if q == 0:# 存储 [价值，价格*重要度]main_parts[i] = [v, v*p]# 附件else:# 存储 [价值，价格*重要度]if q in accessories:accessories[q].append([v, v*p])else:accessories[q] = [[v, v*p]]# {1: [800, 1600], 4: [400, 1200], 5: [500, 1000]}
# print(main_parts)
# {1: [[400, 2000], [300, 1500]]}
# print(accessories)# 初始化动态规划表，dp[j]表示预算在j内的最大满意度
dp = [0] * (N + 1)# 遍历主件
for key, value in main_parts.items():# w表示，一个主件和其附件的各种可能组合的总价格，# 如[800, 1200, 1100, 1500]， 800表示主件，# 1200表示主件+附件1，1100表示主件+附件2，1500表示主件+附件1+附件2# v表示对应组合的满意度w, v = [], []# 1、主件的价格w.append(value[0])  v.append(value[1])  # 主件的满意度if key in accessories:  # 存在附件# 2、主件+附件1w.append(w[0] + accessories[key][0][0])  v.append(v[0] + accessories[key][0][1])if len(accessories[key]) > 1:  # 附件个数为2# 3、主件+附件2w.append(w[0] + accessories[key][1][0])  v.append(v[0] + accessories[key][1][1])# 4、主件+附件1+附件2w.append(w[0] + accessories[key][0][0] + accessories[key][1][0])  v.append(v[0] + accessories[key][0][1] + accessories[key][1][1])# print(w)# print(v)# 每加入一个组合，都重新遍历一遍，检查是否可以实现最大满意度# j表示预算，从N开始递减10，直至小于-1，即1000, 980, ..., 0for j in range(N, -1, -10):  # 物品的价格是10的整数倍# 使用 enumerate 遍历列表，并打印出索引和对应的元素for k, _ in enumerate(w):# 是否能将该组合_放入# 包含该组合（主件+附件）的价格之后，还有余额，就选中该组合if j - w[k] >= 0:# dp[j]表示当前预算为j的最大满意度# dp[j - w[k]] + v[k]表示把v包含进来# j - w[k]表示剩余的预算# dp[j - w[k]]表示剩余的预算可以实现的最大满意度dp[j] = max(dp[j], dp[j - w[k]] + v[k])print(dp[N])

参考：https://coco56.blog.csdn.net/article/details/124463397

by 软件工程小施同学

这篇关于华为机考入门python3--（16）牛客16-购物单最大满意度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---