题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1−5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为 vj​，重要度为 wj​，共选中了 k 件物品，编号依次为 j1​,j2​,…,jk​，则所求的总和为：

vj1​​×wj1​​+vj2​​×wj2​​…+vjk​​×wjk​​

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 2 个正整数，用一个空格隔开：n,m（n<30000,m<25）其中 n 表示总钱数，m 为希望购买物品的个数。

从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v,p（其中 v 表示该物品的价格 (v≤10000)，p 表示该物品的重要度（1≤p≤5）。

输出格式

1 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

输入输出样例

输入 #1复制

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

输出 #1复制

3900

说明/提示

NOIP 2006 普及组 第二题

解析

一、问题本质分析

题目可抽象为：给定预算N元和m件物品（每件有价格v和重要度p），在不超过预算前提下，最大化∑(v[i]×p[i])。这是典型的01背包问题变种，其中物品价值=价格×重要度。

二、动态规划建模

1. 状态定义

设dp[j]表示使用j元能获得的最大价值总和

2. 状态转移方程

dp[j] = max(dp[j], dp[j-v[i]] + v[i]*p[i])  // j >= v[i]

3. 空间优化

使用一维数组逆向更新：

for(int i=1; i<=m; i++)
    for(int j=N; j>=v[i]; j--)
        dp[j] = max(dp[j], dp[j-v[i]] + v[i]*p[i]);

三、完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, m;  // 总钱数和物品数
    cin >> N >> m;
    
    vector<int> v(m+1), p(m+1);  // 价格和重要度
    for(int i=1; i<=m; i++) 
        cin >> v[i] >> p[i];
    
    vector<int> dp(N+1, 0);  // DP数组
    
    for(int i=1; i<=m; i++) {
        for(int j=N; j>=v[i]; j--) {
            dp[j] = max(dp[j], dp[j-v[i]] + v[i]*p[i]);
        }
    }
    
    cout << dp[N];  // 输出最大价值
    return 0;
}

代码采用经典01背包框架，变量命名清晰体现业务含义

四、逐行代码批注

1. ‌输入处理‌：

   • v/p数组从1开始存储（符合日常计数习惯）
   • 同步读取价格和重要度

2. ‌DP初始化‌：

   • dp数组大小为N+1（0元到N元）
   • 初始值为0表示未选择任何物品

3. ‌核心逻辑‌：

   • 外层循环遍历物品（1~m）
   • 内层逆序更新金额（N~v[i]）
   • 状态转移计算最大价值

4. ‌输出结果‌：

   • dp[N]即为预算内的最大价值

五、复杂度分析

操作	时间复杂度	空间复杂度
输入处理	O(m)	O(m)
DP过程	O(mN)	O(N)
输出结果	O(1)	O(1)

六、算法正确性证明

1. ‌无后效性保证‌：逆序更新避免重复选择
2. ‌最优子结构‌：dp[j]始终记录历史最优解
3. ‌边界处理‌：j>=v[i]确保不超预算

七、测试用例验证

输入：
1000 5
800 2
400 5
300 5
400 3
200 2

输出：
3900

解释：选择第2、3、4件物品，总花费1100超预算，实际最优解为第2、3、5件：400×5+300×5+200×2=3900

八、总结与提升

1. ‌核心收获‌：

   • 掌握01背包的空间优化技巧
   • 理解价值计算的灵活变形

2. ‌同类问题‌：

   • 洛谷P1048 采药（标准01背包）
   • 洛谷P1164 小A点菜（求方案数）

3. ‌优化方向‌：

   • 当N极大时可用贪心近似
   • 物品可分割时用分数背包

4. ‌易错点‌：

   • 忘记逆序更新导致错误
   • 价值计算遗漏重要度系数

该解法完美展示了如何将实际问题抽象为背包模型。建议进一步练习：

1. 尝试输出具体选择的物品
2. 修改为完全背包问题解法
3. 研究二进制优化的多重背包实现

理解背包问题的本质后，可解决约70%的NOIP动态规划题型，是算法竞赛的必备技能。