动态规划之【背包DP】第15课：分组背包DP应用案例实践2

动态规划之【背包DP】第15课分组背包DP应用案例实践2题目描述金明今天很开心家里购置的新房就要领钥匙了新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过n nn元钱就行”。今天一早金明就开始做预算了他把想买的物品分为两类主件与附件附件是从属于某个主件的下表就是一些主件与附件的例子主件附件电脑打印机扫描仪书柜图书书桌台灯文具工作椅无如果要买归类为附件的物品必须先买该附件所属的主件。每个主件可以有0 00个、1 11个或2 22个附件。每个附件对应一个主件附件不再有从属于自己的附件。金明想买的东西很多肯定会超过妈妈限定的n nn元。于是他把每件物品规定了一个重要度分为5 55等用整数1 ∼ 5 1 \sim 51∼5表示第5 55等最重要。他还从因特网上查到了每件物品的价格都是10 1010元的整数倍。他希望在不超过n nn元的前提下使每件物品的价格与重要度的乘积的总和最大。设第j jj件物品的价格为v j v_jvj​重要度为w j w_jwj​共选中了k kk件物品编号依次为j 1 , j 2 , … , j k j_1,j_2,\dots,j_kj1​,j2​,…,jk​则所求的总和为v j 1 × w j 1 v j 2 × w j 2 ⋯ v j k × w j k v_{j_1} \times w_{j_1}v_{j_2} \times w_{j_2} \dots v_{j_k} \times w_{j_k}vj1​​×wj1​​vj2​​×wj2​​⋯vjk​​×wjk​​请你帮助金明设计一个满足要求的购物单。输入格式第一行有两个整数分别表示总钱数n nn和希望购买的物品个数m mm。第2 22到第( m 1 ) (m 1)(m1)行每行三个整数第( i 1 ) (i 1)(i1)行的整数v i v_ivi​p i p_ipi​q i q_iqi​分别表示第i ii件物品的价格、重要度以及它对应的的主件。如果q i 0 q_i0qi​0表示该物品本身是主件。输出格式输出一行一个整数表示答案。输入输出样例 1输入 11000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0输出 12200数据规模与约定对于全部的测试点保证1 ≤ n ≤ 3.2 × 10 4 1 \leq n \leq 3.2 \times 10^41≤n≤3.2×1041 ≤ m ≤ 60 1 \leq m \leq 601≤m≤600 ≤ v i ≤ 10 4 0 \leq v_i \leq 10^40≤vi​≤1041 ≤ p i ≤ 5 1 \leq p_i \leq 51≤pi​≤50 ≤ q i ≤ m 0 \leq q_i \leq m0≤qi​≤m答案不超过2 × 10 5 2 \times 10^52×105。思路分析本题是带有依赖关系的背包问题树形依赖每个主件最多两个附件。核心思路将每个主件及其附件视为一个物品组组内包含以下 4 种购买方案若附件不存在则跳过只买主件买主件 附件1买主件 附件2买主件 附件1 附件2由于附件必须与主件同时购买且每个主件只能选择一种方案或不选因此问题转化为分组背包总容量为总钱数n每组内至多选一个物品即上述方案求总价值价格×重要度的最大值算法流程读入n, m及每件物品的价格v[i]、重要度p[i]、主件编号q[i]。对于每个附件将其加入对应主件的附件列表a[主件][cnt] 附件编号。初始化dp[j]表示花费j元能获得的最大价值。遍历所有物品只处理主件q[i]0对于当前主件i获取其附件c1, c2若存在。采用01 背包的逆序循环j n ~ v[i]依次尝试上述 4 种购买组合用dp[j] max(dp[j], dp[j - cost] value)更新。由于j从大到小且所有组合的cost v[i]所以j - cost j这些更小的容量尚未被当前主件的任何组合更新从而保证了同一主件的不同组合不会相互叠加。输出dp[n]。时间复杂度O(m * 4 * n)空间复杂度O(n m)满足题目限制。代码实现#includebits/stdc.husingnamespacestd;intdp[32010];// dp[j]花费j元的最大价值intv[65],p[65],q[65];// v:价格, p:重要度, q:主件编号(0表示主件)inta[65][5],cnt[65];// a[i][1~cnt[i]]: 主件i的附件编号intmain(){intn,m;cinnm;// n:总钱数, m:物品数// 读入物品并记录附件归属for(inti1;im;i){cinv[i]p[i]q[i];if(q[i]){// 附件a[q[i]][cnt[q[i]]]i;// 加入主件的附件列表}}// 遍历所有物品只处理主件for(inti1;im;i){if(q[i])continue;// 跳过附件// 01背包逆序循环保证每个主件的组合互斥for(intjn;jv[i];j--){intxi;// 主件下标intc1a[i][1];// 第一个附件可能为0intc2a[i][2];// 第二个附件可能为0// 策略1只买主件dp[j]max(dp[j],dp[j-v[x]]v[x]*p[x]);// 策略2主件 附件1如果存在if(c1jv[x]v[c1])dp[j]max(dp[j],dp[j-v[x]-v[c1]]v[x]*p[x]v[c1]*p[c1]);// 策略3主件 附件2如果存在if(c2jv[x]v[c2])dp[j]max(dp[j],dp[j-v[x]-v[c2]]v[x]*p[x]v[c2]*p[c2]);// 策略4主件 两个附件如果都存在if(c1c2jv[x]v[c1]v[c2])dp[j]max(dp[j],dp[j-v[x]-v[c1]-v[c2]]v[x]*p[x]v[c1]*p[c1]v[c2]*p[c2]);}}coutdp[n]endl;return0;}功能分析1. 程序功能在给定总钱数n和物品列表含主附件关系的前提下计算能获得的最大价格 × 重要度之和。2. 核心逻辑依赖处理使用a[i][1..cnt[i]]存储每个主件的附件编号便于快速访问。分组背包实现不显式构造组合数组而是在 DP 循环中直接枚举四种可能的购买方案利用j的逆序循环保证同一主件的方案不会相互干扰因为j - cost总是更小的容量尚未被当前主件的更新覆盖。状态转移dp[j] max(dp[j], dp[j - cost] value)其中cost和value分别为当前方案的总价格和总价值。3. 复杂度时间复杂度最坏情况O(m * 4 * n) ≈ 60 * 4 * 32000 ≈ 7.68e6在 C 环境下运行极快。空间复杂度O(n m)dp数组约 32005 个int结构数组约 65 个元素内存占用很小。完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}