牛客网 HJ16 购物单

牛客网 HJ16 购物单题目链接https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4一、原题完整陈述题目描述王强拿年终奖购物物品分为主件、附件两类附件不能单独购买想买附件必须先买它对应的主件一个主件最多0、1、2个附件附件不会再有自己的附件每件物品只能买一次每件物品价格都是10的整数倍每件物品有重要度1~5满意度 所有购买物品的价格 × 重要度相加总和给定总预算求不超过预算条件下最大满意度。核心关键点不能单独买附件主件附件是捆绑选择属于分组背包每组里面只能选一种方案或者啥都不选输入描述第一行两个整数N总预算、m物品总数后面m行每行3个整数v p qv物品价格p物品重要度q所属主件编号q0代表这个物品是主件q≠0代表是附件q是它所属主件的输入序号物品编号从1开始输出描述输出一个整数最大满意度样例输入1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0样例输出2200解释物品1主件800附件1400附件2300物品4主件400物品5主件500最优方案买物品1(800)它的两个附件(400300)总花费1500超预算选物品1(800)附件1(400) 花费1200超预算选物品4(400)物品5(500)花费900满意度4003 5002 2200。二、费曼学习法拆解破解思路讲给小白费曼思想不用专业术语像给完全不懂动态规划的同学讲明白这道题。1. 把题目翻译成大白话你有一笔钱想买东西。有些东西是配件比如电脑主件打印机、扫描仪是电脑附件。不能只买打印机必须先买电脑。电脑最多配2个附件。每样东西买一次。每样东西有一个分数价格×重要度在钱花不完的前提下让总分尽可能最大。普通01背包每个物品就2种选择买 / 不买。但本题不一样主件附件是捆绑套餐套餐有4种合法购买方案一组套餐4个方案4选1或者全都不买方案1只买主件方案2主件 附件1方案3主件 附件2方案4主件 附件1 附件2重点同一组套餐4种方案最多只能挑其中1种。这就是分组背包每组内方案互斥。2. 观察题目隐藏的小福利所有物品价格都是10的倍数。我们可以所有价格 /10预算也除以10。好处数组长度缩小10倍循环次数变少节省内存程序跑更快。最后算出来的满意度不受影响因为满意度公式是价格×重要度价格同比例缩放价值不变。3. 动态规划DP数组含义dp[j]当预算为j已经除以10的时候可以拿到的最大满意度。dp数组初始化全部0没钱的时候满意度为0。状态转移逻辑分组背包遍历每一组每一个主件套餐倒序遍历预算容量01背包经典操作防止同一个套餐被重复多次购买对套餐里面的每一个可选方案如果当前预算足够买下这个方案那么dp[j] max(原来dp[j], dp[j - 方案花费] 方案满意度)含义二选一保留更大满意度① 不选这个套餐方案保持原来dp[j]② 选这个套餐方案花掉方案的钱剩下钱的最优结果 当前方案的满意度为什么倒序正序遍历会让同一个套餐被反复多次选取相当于重复买同一台电脑违反题目每件物品只能买一次。倒序从大预算往小预算遍历保证每个套餐只使用一次。4. 整体解题步骤拆解读取预算N物品数量m预算N N//10价格全部后续除以10建立数据结构存储每个主件以及它的附件列表循环读取m个物品如果q0 → 主件存入主件列表如果q≠0 → 附件加到对应主件的附件列表对每一个主件生成它全部合法4种购买套餐组合初始化dp数组长度总预算1初始值全部0遍历每一组套餐每一个主件对应的4种方案倒序遍历预算容量j遍历套餐内所有组合如果j 组合花费更新dp[j]取最大值全部套餐处理完后dp[N]就是最大满意度直接输出。5. 边界情况思考测试坑点主件没有附件套餐只有1种方案只买主件主件只有1个附件套餐只有2种方案主件主件附件预算太少任何主件都买不起答案为0物品价格刚好等于预算附件不能脱离主件单独作为方案。6. 手动模拟小样例理解DP样例预算1000除以10变成100。物品1号主件800 → 8价值1600附件1:400→4价值2000附件2:300→3价值15004号主件400→4价值12005号主件500→5价值10004号套餐只有1个方案花费4价值12005号套餐只有1个方案花费5价值1000当预算j9459总价值2200 → dp[9]2200对应原始预算900元就是样例答案。三、Python完整代码 每行详细注释# HJ16 购物单 牛客华为机试 分组背包DP# 题目特点主件附件捆绑购买附件不可单独购买属于分组背包defmain():# 读取第一行输入总预算N物品总数m# input().split()读取字符串map转成两个整数N,mmap(int,input().split())# 题目所有价格都是10的倍数预算除以10压缩规模减少数组大小NN//10# 定义列表存储主件信息每个主件元素 [主件价格, 主件价值, [附件列表]]# 附件列表里面每一项是 [附件价格附件价值]main_goods[]# 循环读取m件物品信息编号从1开始foridxinrange(1,m1):# v价格p重要度q所属主件编号v,p,qmap(int,input().split())# 价格除以10和预算保持同一缩放vv//10# 满意度 价格 × 重要度valuev*pifq0:# q0当前物品是主件加入主件列表附件列表初始为空main_goods.append([v,value,[]])else:# q≠0是附件q是所属主件的序号主件在main_goods下标 q-1# 把这个附件的价格、价值追加到对应主件的附件列表main_goods[q-1][2].append([v,value])# 初始化dp数组dp[j] 预算j下最大满意度# 数组长度 N1全部初始化为0预算0满意度一定是0dp[0]*(N1)# 遍历每一组每一个主件作为分组背包里的一组formain_price,main_val,attach_listinmain_goods:# 生成当前主件的全部合法购买组合套餐方案 combo[]# 方案1只买主件combo.append([main_price,main_val])# 判断附件数量追加其他合法组合attach_countlen(attach_list)ifattach_count1:a1_price,a1_valattach_list[0]# 方案2主件 附件1combo.append([main_pricea1_price,main_vala1_val])ifattach_count2:a1_price,a1_valattach_list[0]a2_price,a2_valattach_list[1]# 方案3主件 附件2combo.append([main_pricea2_price,main_vala2_val])# 方案4主件 附件1 附件2combo.append([main_pricea1_pricea2_price,main_vala1_vala2_val])# 分组背包核心倒序遍历预算01背包 # 倒序从总预算N向下循环到0防止同一套餐重复多次选取forjinrange(N,-1,-1):# 遍历本组内每一个可选套餐方案forcost,valincombo:# 判断当前预算j能不能买下这个套餐预算 套餐花费ifjcost:# 状态转移取两种选择的最大值# 选择1不买套餐dp[j]保持原值# 选择2购买套餐剩下预算 j-cost 的最优值 当前套餐价值dp[j]max(dp[j],dp[j-cost]val)# dp[N] 就是压缩预算后的最大满意度满意度不用还原*10print(dp[N])# 程序入口运行主函数if__name____main__:main()样例输入测试1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0运行输出2200重要提醒满意度是v//10 * p原始v除以10之后v*p和原来(v//10)*10 * p/10 结果一致价值不用乘以10还原很多新手在这里踩坑。四、应用场景举例场景1电脑装机选配最贴合原题预算有限选购电脑主机主件可以选配硬盘、内存附件。不能单独买内存必须先买主机。不同套餐只主机、主机硬盘、主机内存、主机硬盘内存。目标预算内综合性能价值最大化。完全就是本题模型。场景2电商套餐捆绑营销商品主商品可选配件手机耳机、手机壳膜配件不能单独下单。给定预算选择套餐最大化用户收益/评分。后台用分组背包做推荐最优组合。场景3项目投资选择一个主项目可以附带1~2个子项目子项目不能脱离主项目单独投资。每组主项目子项目只能选一种投资方案资金有限最大化总收益。场景4课程选课一门主课可以搭配最多两门选修课选修课不能单独选。每一组课程包只能选一种组合总课时预算上限最大化学分收益。场景5零件采购机器主体为主件配套零件是附件采购附件必须采购主体每个主体最多2个配件采购资金有限最大化整套设备综合效能。五、费曼复盘总结复述学到的内容HJ16购物单本质带依赖关系的01背包 → 转化成分组背包。核心转化技巧把主件附件所有合法捆绑购买方案打包成一组套餐同一组套餐里面最多只能挑选1套方案。关键点价格全部是10倍数可以压缩预算数组优化性能01背包一维dp数组预算必须倒序遍历避免重复选取同一套餐分组背包循环顺序外层遍历组中层倒序预算内层遍历组内各个方案附件不能单独构成方案只能依附主件。知识点清单动态规划、一维DP优化、01背包、分组背包、方案枚举。拓展补充可选常见错误坑清单递归记忆化搜索版本代码二维DP版本方便新手理解dp原始定义