洛谷 P1060 [NOIP 2006 普及组] 开心的金明

0题目原文（本地存了一份）

题目描述

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

设第 j 件物品的价格为 vⱼ，重要度为 wⱼ，共选中了 k 件物品， 编号依次为 j₁, j₂, …, j_k，则所求的总和为：

    v[j1] × w[j1] + v[j2] × w[j2] + … + v[jk] × w[jk]

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

输入格式

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

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

输出格式

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

说明/提示

NOIP 2006 普及组 第二题

输入输出样例

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

3900

1★ 关键的一步：价值 = 价格 × 重要度

这道题在题单里的作用是「确认自己是真的会了」—— 它是第 23 章 那份 fast.cpp 的原样搬运，只是把「价值」换成了一个要自己算的量：

// P1060 [NOIP 2006 普及组] 开心的金明 —— ★ 这一版就能 AC
//
// 题意：总钱数 n，m 件物品，第 j 件价格 v，重要度 p（1~5）；
//       在不超过 n 元的前提下，最大化 Σ v × p。
//
// ★ 这道题是纯模板：**价值 = 价格 × 重要度**，剩下的和[第 23 章](/ch/23-knapsack-01/)
//   那份 fast.cpp 一个字都不差。它在题单里的作用是「确认自己是真的会了」。
//
// ⚠ 而这道题真正会咬人的地方**一个都不在算法里**（解析页把三条都量过了）：
//   ① 第一行是「n m」＝「**总钱数** 在前，**物品数** 在后」—— 和直觉正好相反；
//   ② 价值是 v × p，不是 p；
//   ③ 一维必须倒序。
//
// ★ 顺带一条算术：答案 = Σ v×p ≤ 5 × Σ v ≤ 5n < 1.5 × 10^5 ——
//   题面写的「< 10^8」松了六百多倍，int 随便够。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;                                  // ⚠ n = 总钱数，m = 物品件数
    if (!(cin >> n >> m)) return 0;

    vector<int> f(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int v, p; cin >> v >> p;
        int w = v * p;                         // ★ 价值 = 价格 × 重要度
        for (int j = n; j >= v; j--)           // 倒序：每件只能买一次
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[n] << "\n";
    return 0;
}

点「运行 ▶」看结果

2★★★ m < 25 这个数：这道题的顶格对拍，参照物可以就是暴力

题面写着 m < 25 —— 最多 24 件物品。把它乘出来：

    2^24 = 16 777 216

3三个错法，官方样例一个不剩全挡住了

4★★ 把题面那几句约束称一称

按第 12 章那套判据（情报 / 命门 / 噪声，判法是同一个动作： 造一档违反它的数据，看有没有任何一版的行为变了）：

5度量程序和生成器

6一页纸