[NOIP2006 提高组] 金明的预算方案
题目描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 $n$ 元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:
主件 | 附件 |
---|---|
电脑 | 打印机,扫描仪 |
书柜 | 图书 |
书桌 | 台灯,文具 |
工作椅 | 无 |
如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件,附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 $n$ 元。于是,他把每件物品规定了一个重要度,分为 $5$ 等:用整数 $1 \sim 5$ 表示,第 $5$ 等最重要。他还从因特网上查到了每件物品的价格(都是 $10$ 元的整数倍)。他希望在不超过 $n$ 元的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第 $j$ 件物品的价格为 $v_j$,重要度为$w_j$,共选中了 $k$ 件物品,编号依次为 $j_1,j_2,\dots,j_k$,则所求的总和为:
$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行有两个整数,分别表示总钱数 $n$ 和希望购买的物品个数 $m$。
第 $2$ 到第 $(m + 1)$ 行,每行三个整数,第 $(i + 1)$ 行的整数 $v_i$,$p_i$,$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$,表示该物品本身是主件。如果 $q>0$ ,表示该物品为附件,q是所属主件的编号。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出 #1
2200
提示
数据规模与约定
对于全部的测试点,保证 $1 \leq n \leq 3.2 \times 10^4$,$1 \leq m \leq 60$,$0 \leq v_i \leq 10^4$,$1 \leq p_i \leq 5$,$0 \leq q_i \leq m$,答案不超过 $2 \times 10^5$。
NOIP 2006 提高组 第二题
题解
本题是分组背包+01背包的变形 每个物品数量只有一个
并且每个主件从属只有0个 1个 2个三种情况 大大降低了复杂度
读题要看清 $ q{i} = 0 $ 的时候他就是主件 他的附件在它下面输入
f[i][j]表示选择前i个主件且预算为j时的 价格重要度 最大值
这里的预算就是背包容积 价格就是物品体积 重要度价格 就是当前价值
我们利用01背包的思想去分析 无非就五种情况
- 不选该主件
f[i][j] = f[i - 1][j];
- 选择该主件,但不选其附件
f[i][j] = max(f[i - 1][j], f[i - 1][j - maw[i]] + mav[i]);
- 选择该主件,并选择该主件的一号附件 (选择的前提是附件存在)
f[i][j] = max(f[i - 1][j], f[i - 1][j - maw[i] - anw[i][0]] + mav[i] + anv[i][0]);
- 选择该主件,并选择该主件的二号附件
f[i][j] = max(f[i - 1][j], f[i - 1][j - maw[i] - anw[i][1]] + mav[i] + anv[i][1])
- 选择该主件,并选择该主件的二号和三号附件
f[i][j] = max(f[i - 1][j], f[i][j], f[i - 1][j - maw[i] - anw[i][0]- anw[i][1]] + mav[i] + anv[i][0] + anv[i][1])
由于max函数不能同时比较三个值 代码里我们分成两个函数比较
二维背包代码
我要死了 debug了两个小时 代码一旦变长 很多地方就容易写错
很重要的一行代码!
当前i不是主件时,我们需要将主件里求出的f[i][j]
传递给当前的附件f[][]
状态
这样在运行到下一个主件时我们在循环内利用的f[i - 1][j]
才是有效的
才能继承到上一个主件内算出的状态f[][]
否则f[i - 1][j]
会是0
for (int j = 0; j <= m; j ++ ) f[i][j] = max(f[i][j], f[i - 1][j]);
#include <bits/stdc++.h>
using namespace std;
const int N = 70, M = 32010;
int f[N][M];
int maw[N], mav[N]; //分别存第i个主件的价格 和 价格*重要度
int anw[N][2], anv[N][2]; //分别存第i个主件的附件的价格 和 价格*重要度, 附件最多有2个
int cnt[N]; //存第i个主件的附件个数(可能不足两个)
int n, m; //所有物品个数 和 总预算
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ )
{
int v, p, q;
scanf("%d%d%d", &v, &p, &q);
if (!q) //如果当前物品是主件
{
maw[i] = v;
mav[i] = v * p;
}
else
{
cnt[q] ++ ; //读到一个附件 该主件的附件数目++
anw[q][cnt[q]] = v;
anv[q][cnt[q]] = v * p;
}
}
//cout << maw[3] << endl;
//cout << maw[1] + anw[1][1] << endl;
for (int i = 1; i <= n; i ++ )
{
if (maw[i]) //当前物品编号代表主件时
{ //注意我们只对主件进行循环 因为选了主件才能选到他的附件 这也是本题的特殊点
for (int j = 0; j <= m; j ++ ) //这里要加一个 maw[i] != 0 的判断条件 原因是确保当前i遍历到的是主件 我们在主件的组内进行操作
{
if (j < maw[i]) f[i][j] = f[i - 1][j]; //当当前主件不选时
//这里底下if判断的顺序怎样都可以 因为我们会比较上一个if里算出的f[i][j]和当前的哪个大
if (j >= maw[i]) f[i][j] = max(f[i][j], max(f[i -1][j], f[i - 1][j - maw[i]] + mav[i])); //只选主件
if (j >= maw[i] + anw[i][1]) f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - maw[i] - anw[i][1]] + mav[i] + anv[i][1])); //多选1号附件 要利用两层max()将其与之前求出的f[i][j]比较大小 因为max()只能比较两个数的大小
if (j >= maw[i] + anw[i][2]) f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - maw[i] - anw[i][2]] + mav[i] + anv[i][2])); //多选2号附件 注意这里不用考虑1号或2号附件存不存在 若不存在他的anw和anv就等于0 相当于没改变f[][]
if (j >= maw[i] + anw[i][1] + anw[i][2]) f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - maw[i] - anw[i][1] - anw[i][2]] + mav[i] + anv[i][1] + anv[i][2])); //主件和他的两个附件都选
//cout << f[1][m] << endl;
}
}
//很重要的一行代码! 当前i不是主件时,我们需要将主件里求出的f[i][j]传递给当前的附件f[][]状态 这样在运行到下一个主件时我们在循环内利用的f[i - 1][j]才是有效的 才不会是0
for (int j = 0; j <= m; j ++ ) f[i][j] = max(f[i][j], f[i - 1][j]);
}
printf("%d\n", f[n][m]);
return 0;
}
一维优化代码
#include <bits/stdc++.h>
using namespace std;
const int N = 70, M = 32010;
int f[M];
int maw[N], mav[N];
int anw[N][2], anv[N][2];
int cnt[N];
int n, m;
int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ )
{
int v, p, q;
scanf("%d%d%d", &v, &p, &q);
if (!q)
{
maw[i] = v;
mav[i] = v * p;
}
else
{
cnt[q] ++ ;
anw[q][cnt[q]] = v;
anv[q][cnt[q]] = v * p;
}
}
for (int i = 1; i <= n; i ++ )
{
if (maw[i])
{
for (int j = m; j >= maw[i]; j -- ) //01背包要倒序
{
f[j] = max(f[j], f[j - maw[i]] + mav[i]); //这里f[i - 1][j]和f[i][j] 都变成f[j] 不需要用两层max()
if (j >= maw[i] + anw[i][1]) f[j] = max(f[j], f[j - maw[i] - anw[i][1]] + mav[i] + anv[i][1]); //多选1号附件 要利用两层max()将其与之前求出的f[i][j]比较大小 因为max()只能比较两个数的大小
if (j >= maw[i] + anw[i][2]) f[j] = max(f[j], f[j - maw[i] - anw[i][2]] + mav[i] + anv[i][2]); //多选2号附件 注意这里不用考虑1号或2号附件存不存在 若不存在他的anw和anv就等于0 相当于没改变f[][]
if (j >= maw[i] + anw[i][1] + anw[i][2]) f[j] = max(f[j], f[j - maw[i] - anw[i][1] - anw[i][2]] + mav[i] + anv[i][1] + anv[i][2]); //主件和他的两个附件都选
}
}
}
printf("%d\n", f[m]);
return 0;
}