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。
• 价值总和计算公式： $v[j1] \times w[j1] + v[j2] \times w[j2] + \dots + v[jk] \times w[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] = \max(dp[j], dp[j - v] + v \times p)$其中：

• dp[j] 代表 ​总预算为 j 时的最大价值​。
• 遍历物品 i，若选择它，则 ​**当前预算 j 需要减去 v[i]**​，并加上它的价值 v[i] × p[i]。

优化策略

1. ​**采用倒序遍历 j**​，确保每个物品 i 只被选择 0 或 1 次，避免重复选择。
2. ​时间复杂度​：
   • 物品数量 m ≤ 25，总预算 N ≤ 30000，时间复杂度 ​**O(m × N)**​，最多约 750000 次计算，在 1 秒内可接受。

---

时间复杂度分析

步骤	复杂度
读取输入	O(m)
计算最大价值	O(m × N)
总复杂度

由于 m ≤ 25 且 N ≤ 30000，即 750000 次计算，动态规划方法是可行的。