P1064 金明的预算方案网页链接P1064 金明的预算方案题目描述金明今天很开心家里购置的新房就要领钥匙了新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过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​w i w_iwi​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 ≤ w i ≤ 5 1 \leq w_i \leq 51≤wi​≤50 ≤ q i ≤ m 0 \leq q_i \leq m0≤qi​≤m答案不超过2 × 10 5 2 \times 10^52×105。NOIP 2006 提高组 第二题解题思路本题是有依赖的背包问题分组背包。物品分为主件和附件购买附件必须先购买其所属主件且每个主件最多有 2 个附件。由于附件数量极少可以将每个主件及其可能的附件组合视为一个“物品组”组内包含若干种互斥的购买方案然后对每组做一次 0/1 背包决策。1. 问题等价转化每个主件i有价格v[i][0]、重要度w[i][0]以及至多两个附件价格和重要度分别记为v[i][1], w[i][1]和v[i][2], w[i][2]。对于主件i可选的购买方案有均必须包含主件只买主件主件 附件 1主件 附件 2主件 附件 1 附件 2。这些方案互斥只能选择其中一种。问题转化为在总预算n内从所有主件对应的方案组中选择一组方案使得总价值价格 × 重要度最大。这是一个典型的分组背包问题每个主件对应一个组组内物品为上述 4 种方案。2. 算法实现二维 DP设d[i][j]表示考虑前i个主件实际按物品编号遍历跳过附件预算为j时能获得的最大价值。初始化d[0][j] 0。对于每个物品i从 1 到m先继承上一状态d[i][j] d[i-1][j]。如果i是主件即v[i][0] 0则尝试四种方案若当前预算j足够则更新d[i][j] max(d[i][j], d[i-1][j - 方案总价] 方案总价值)如果i是附件则不做额外处理因为附件已经归入其主件的方案中直接继承上一行即可。最终答案d[m][n]。3. 复杂度分析时间复杂度物品数m ≤ 60预算n ≤ 32000。每个主件最多枚举 4 种方案总状态转移次数约m × n × 4即60 × 32000 × 4 ≈ 7.7 × 10^6完全可行。空间复杂度二维 DP 数组d[65][32005]约2 × 10^6个long long空间可接受。总结利用每个主件附件数量极少的特点将主件及其附件的所有合法购买组合枚举出来转化为分组背包。按物品编号顺序进行 DP遇到附件直接跳过继承状态遇到主件则尝试其所有组合。该方法简洁高效完美解决了有依赖的背包问题。代码简要说明数组定义a[i][0], b[i][0]主件i的价格和重要度。a[i][1], b[i][1]附件 1 的价格和重要度。a[i][2], b[i][2]附件 2 的价格和重要度。d[i][j]前i个物品、预算j的最大价值。输入处理读入n, m对于每个物品若q0则为主件存入a[i][0], b[i][0]否则为附件根据该主件已有的附件数量存入a[q][1]或a[q][2]。DP 过程外层循环i从 1 到m内层j从 0 到n。先继承d[i][j] d[i-1][j]。若i是主件则依次判断四种组合是否能在预算j内购买并更新最大值。输出d[m][n]即为答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m;ll a[65][3],b[65][3],d[65][32005];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;im;i){ll x,y,z;cinxyz;if(z){if(a[z][1]){a[z][2]x;b[z][2]y;}else{a[z][1]x;b[z][1]y;}}else{a[i][0]x;b[i][0]y;}}for(ll i1;im;i){for(ll j0;jn;j){d[i][j]d[i-1][j];if(a[i][0]j)d[i][j]max(d[i][j],d[i-1][j-a[i][0]]a[i][0]*b[i][0]);if(a[i][0]a[i][1]j)d[i][j]max(d[i][j],d[i-1][j-a[i][0]-a[i][1]]a[i][0]*b[i][0]a[i][1]*b[i][1]);if(a[i][0]a[i][2]j)d[i][j]max(d[i][j],d[i-1][j-a[i][0]-a[i][2]]a[i][0]*b[i][0]a[i][2]*b[i][2]);if(a[i][0]a[i][1]a[i][2]j)d[i][j]max(d[i][j],d[i-1][j-a[i][0]-a[i][1]-a[i][2]]a[i][0]*b[i][0]a[i][1]*b[i][1]a[i][2]*b[i][2]);}}coutd[m][n];return0;}