#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
  • 价值总和计算公式: v[j1]×w[j1]+v[j2]×w[j2]++v[jk]×w[jk]v[j1] \times w[j1] + v[j2] \times w[j2] + \dots + v[jk] \times w[jk] * 表示乘法运算)

请你帮助金明设计一个最优的购物单,使得价值总和最大。


输入格式

  • 第一行 包含两个整数 Nm,用空格隔开:
    • NN < 30000):表示总预算(最大可花费金额)。
    • mm < 25):表示希望购买的物品数量。
  • 接下来的 m​:
    • 每行包含两个整数 vp
      • vv ≤ 10000):该物品的 ​价格​。
      • p1 ≤ p ≤ 5):该物品的 ​重要度​。

输出格式

  • 输出一个正整数,表示 ​不超过预算 N 的最大总价值​。

输入输出示例

输入示例 1

1000 5
800 2
400 5
300 5
400 3
200 2

输出示例 1

3900

解释

可行方案:

  • 购买物品 400 5400 3,总花费 800 元,总价值 400×5 + 400×3 = 3200
  • 购买物品 300 5200 2,总花费 500 元,总价值 300×5 + 200×2 = 1700
  • 购买物品 800 2,总花费 800 元,总价值 800×2 = 1600
  • 最优方案​:购买 400 5300 5200 2,总花费 900 元,总价值 400×5 + 300×5 + 200×2 = 3900

题目分析与解法

这是一个 ​0-1 背包问题​,其中:

  • 背包容量N(总预算)。
  • 物品m 件物品,每个物品只能选择 01 次。
  • 价值v × p
  • 选择目标​:在不超过 N 的情况下,使 ​总价值最大​。

动态规划解法

定义 dp[j] 表示 ​总预算不超过 j 时的最大价值​,状态转移方程:

dp[j]=max(dp[j],dp[jv]+v×p)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 只被选择 01 次,避免重复选择。
  2. 时间复杂度​:
    • 物品数量 m ≤ 25,总预算 N ≤ 30000,时间复杂度 ​**O(m × N)**​,最多约 750000 次计算,在 1 秒内可接受。

时间复杂度分析

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

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