#10172. Happy Jinming / 开心的金明
Happy Jinming / 开心的金明
Problem : Happy Jinming / 开心的金明
版权信息:NOIP 2006 普及组 第二题
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
开心的金明 | 1 sec | 1024 MB | 5 points |
题目描述
金明今天非常开心,因为家里购置的新房即将领取钥匙,新房里有一个宽敞的房间专门属于他。更让他兴奋的是,妈妈告诉他:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 N
元钱就行。”
于是,金明开始列出他想买的物品清单,但他发现自己想买的东西太多了,远远超过 N
元的预算。
为了挑选最合适的物品,他为每件物品规定了 重要度,共分为 5
等(用整数 1~5
表示,5
表示最重要)。此外,他还查到了每件物品的 价格(整数)。
目标:在不超过 N
元(可以等于 N
元)的前提下,选择一部分物品,使得它们的 价值总和最大。
价值计算方式:
- 设第
j
件物品的价格为v[j]
,重要度为w[j]
。 - 设选中了
k
件物品,编号依次为j1, j2, ..., jk
。 - 价值总和计算公式: (
*
表示乘法运算)
请你帮助金明设计一个最优的购物单,使得价值总和最大。
输入格式
- 第一行 包含两个整数
N
和m
,用空格隔开:N
(N < 30000
):表示总预算(最大可花费金额)。m
(m < 25
):表示希望购买的物品数量。
- 接下来的
m
行:- 每行包含两个整数
v
和p
:v
(v ≤ 10000
):该物品的 价格。p
(1 ≤ p ≤ 5
):该物品的 重要度。
- 每行包含两个整数
输出格式
- 输出一个正整数,表示 不超过预算
N
的最大总价值。
输入输出示例
输入示例 1
1000 5
800 2
400 5
300 5
400 3
200 2
输出示例 1
3900
解释
可行方案:
- 购买物品
400 5
和400 3
,总花费800
元,总价值400×5 + 400×3 = 3200
- 购买物品
300 5
和200 2
,总花费500
元,总价值300×5 + 200×2 = 1700
- 购买物品
800 2
,总花费800
元,总价值800×2 = 1600
- 最优方案:购买
400 5
、300 5
、200 2
,总花费900
元,总价值400×5 + 300×5 + 200×2 = 3900
题目分析与解法
这是一个 0-1 背包问题,其中:
- 背包容量 为
N
(总预算)。 - 物品 为
m
件物品,每个物品只能选择0
或1
次。 - 价值 为
v × p
。 - 选择目标:在不超过
N
的情况下,使 总价值最大。
动态规划解法
定义 dp[j]
表示 总预算不超过 j
时的最大价值,状态转移方程:
其中:
dp[j]
代表 总预算为j
时的最大价值。- 遍历物品
i
,若选择它,则 **当前预算j
需要减去v[i]
**,并加上它的价值v[i] × p[i]
。
优化策略
- **采用倒序遍历
j
**,确保每个物品i
只被选择0
或1
次,避免重复选择。 - 时间复杂度:
- 物品数量
m ≤ 25
,总预算N ≤ 30000
,时间复杂度 **O(m × N)**,最多约750000
次计算,在1
秒内可接受。
- 物品数量
时间复杂度分析
步骤 | 复杂度 |
---|---|
读取输入 | O(m) |
计算最大价值 | O(m × N) |
总复杂度 |
由于 m ≤ 25
且 N ≤ 30000
,即 750000
次计算,动态规划方法是可行的。