P1064 金明的预算方案【洛谷算法习题】-迪斯科星球

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)(m+1)行，每行三个整数，第( i + 1 ) (i + 1)(i+1)行的整数v i v_ivi，w i w_iwi，q i q_iqi分别表示第i ii件物品的价格、重要度以及它对应的的主件。如果q i = 0 q_i=0qi=0，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0

输出 #1

说明/提示

数据规模与约定

对于全部的测试点，保证1 ≤ n ≤ 3.2 × 10 4 1 \leq n \leq 3.2 \times 10^41≤n≤3.2×104，1 ≤ m ≤ 60 1 \leq m \leq 601≤m≤60，0 ≤ v i ≤ 10 4 0 \leq v_i \leq 10^40≤vi≤104，1 ≤ w i ≤ 5 1 \leq w_i \leq 51≤wi≤5，0 ≤ 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；
3. 主件 + 附件 2；
4. 主件 + 附件 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，对于每个物品，若q=0则为主件，存入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]即为答案。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;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);cin>>n>>m;for(ll i=1;i<=m;i++){ll x,y,z;cin>>x>>y>>z;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 i=1;i<=m;i++){for(ll j=0;j<=n;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]);}}cout<<d[m][n];return0;}

企业官网建设流程全解析