背包问题：购物单问题（牛客HJ6）中等

一、问题描述二、解题思路(好难--看代码注释)背包问题1.第一步先把所有物品全部缓存物品编号1~m2.第二步只遍历主件创建分组记录belong映射记录第几个物品属于第几组主件组下标3.第三步遍历附件此时所有主件都已建好不会越界4.01背包DP数组dp[j]表示花j元的最大满意度# 取出最多两个附件不足补(0,0)# 01背包逆序遍历预算三、代码n,m map(int,input().split()) # 第一步先把所有物品全部缓存物品编号1~m all_goods [] for i in range(1,m1): # 循环 for i in range(m) → i 从 0 开始但题目物品编号是 1、2、3… # 后面附件的 qi 是物品编号≥1belong[qi] 会错位 vi,wi,qi map(int,input().split()) val int(vi)*int(wi) all_goods.append((i,vi,val,qi)) # 第二步只遍历主件创建分组记录belong映射 # 记录第几个物品属于第几组主件组下标 belong [0]*(m1) groups [] for j,vi,val,qi in all_goods: if qi 0: groups.append([vi,val,[]]) belong[j] len(groups)-1 # 第三步遍历附件此时所有主件都已建好不会越界 for k,vi,val,qi in all_goods: if qi ! 0: gid belong[qi] groups[gid][2].append((vi,val)) # append 只能加 1 个元素附件存元组 (vi, val) # 背包问题 # subs 是当前主件自带的附件列表sub1 取第 1 个附件、sub2 取第 2 个附件附件不足就填 (0,0) 占位 # 拆出 v1附件价格、val1附件满意度v2、val2 同理 # plans 打包 4 套合法组合同一组里只能 4 选 1不能同时选多套 # range(n, -1, -1) 就是从总预算 n 开始每次 - 1一路循环到 0。 # 01背包DP数组dp[j]表示花j元的最大满意度 dp [0]*(n1) for g in groups: v0,val0,q0 g # 取出最多两个附件不足补(0,0) # q0 才是附件列表,不能 len(sub1)sub1 还没定义 # 逻辑判断附件列表 q0 的长度 sub1 q0[0] if len(q0)1 else (0,0) # 取第二个附件需要长度2 # 主件没有附件q0 []长度 len(q0)0 # 主件只有 1 个附件q0 [(30,10)]长度 len(q0)1 # 主件有 2 个附件q0 [(30,10),(50,20)]长度 len(q0)2 sub2 q0[1] if len(q0)2 else (0,0) v1,val1 sub1 v2,val2 sub2 plans [ (v0,val0), (v0v1,val0val1), (v0v2,val0val2), (v0v1v2,val0val1val2) ] # 01背包逆序遍历预算 for j in range(n,-1,-1): for cost,score in plans: if j cost: # 现在我手上有 j 元如果我选择这套搭配这套搭配要花 cost 元。 # 那剩下 j-cost 元之前能拿到的最大满意度是 dp[j-cost]加上这套方案的收益 score就是新总满意度。 # 如果这个新满意度比原来 dp[j] 的数值更大就更新它。 dp[j] max(dp[j],dp[j-cost]score) print(max(dp))