【题目来源】
洛谷：P1064 [NOIP 2006 提高组] 金明的预算方案 - 洛谷
【题目描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 \(n\) 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
|---|---|
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 \(0\) 个、\(1\) 个或 \(2\) 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 \(n\) 元。于是，他把每件物品规定了一个重要度，分为 \(5\) 等：用整数 \(1∼5\) 表示，第 \(5\) 等最重要。他还从因特网上查到了每件物品的价格（都是 \(10\) 元的整数倍）。他希望在不超过 \(n\) 元的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 \(j\) 件物品的价格为 \(v_j\)，重要度为 \(w_j\)，共选中了 \(k\) 件物品，编号依次为 \(j_1,j_2,…,j_k\)，则所求的总和为：
\(v_{j_1}×w_{j_1}+v_{j_2}×w_{j_2}+⋯+v_{j_k}×w_{j_k}\) 请你帮助金明设计一个满足要求的购物单。
【输入】
第一行有两个整数，分别表示总钱数 \(n\) 和希望购买的物品个数 \(m\)。
第 \(2\) 到第 \((m+1)\) 行，每行三个整数，第 \((i+1)\) 行的整数 \(v_i\)，\(p_i\)，\(q_i\) 分别表示第 \(i\) 件物品的价格、重要度以及它对应的的主件。如果 \(q_i=0\)，表示该物品本身是主件。
【输出】
输出一行一个整数表示答案。
【输入样例】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
【输出样例】
2200
【算法标签】
《洛谷 P1064 金明的预算方案》 #NOIP提高组# #2006# #动态规划DP# #背包DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 65; // 定义常量 N，表示最大节点数
int h[N], e[N], ne[N], idx; // 邻接表存储树结构，h[u] 表示节点 u 的第一条边的索引，e[idx] 表示边的终点，ne[idx] 表示下一条边的索引，idx 是边的计数器
int n, m; // n 表示总容量，m 表示物品数量
int wi[N], ci[N]; // wi[i] 表示物品 i 的重量，ci[i] 表示物品 i 的价值
int f[N][33000]; // f[u][j] 表示以节点 u 为根的子树中，容量为 j 时的最大价值// 添加边到邻接表
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++; // 将边 (a, b) 添加到邻接表中
}// 深度优先搜索函数
void dfs(int u)
{for (int i = h[u]; i != -1; i = ne[i]) // 遍历节点 u 的所有邻接边{int v = e[i]; // v 是当前边的终点// 初始化 f[v][i]，表示在节点 v 的子树中，容量为 i 时的最大价值for (int i = n - wi[v]; i >= 0; i--)f[v][i] = f[u][i] + ci[v]; // 继承父节点的状态，并加上当前节点的价值dfs(v); // 递归遍历子树// 更新父节点 u 的状态for (int j = n; j >= wi[v]; j--)f[u][j] = max(f[u][j], f[v][j - wi[v]]); // 选择是否将节点 v 加入背包，前者为不选择，后者为选择}
}int main()
{memset(h, -1, sizeof(h)); // 初始化邻接表头数组 hcin >> n >> m; // 输入总容量 n 和物品数量 mfor (int i = 1; i <= m; i++) // 输入每个物品的信息{int x;cin >> wi[i] >> ci[i] >> x; // 输入物品 i 的重量、价值和依赖关系ci[i] *= wi[i]; // 将价值转换为实际价值（价值 = 重量 * 单位价值）add(x, i); // 将物品 i 添加到依赖关系树中}dfs(0); // 从根节点 0 开始深度优先搜索cout << f[0][n] << endl; // 输出以根节点 0 为根的子树中，容量为 n 时的最大价值return 0;
}
【运行结果】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200