[NOIP 2006 普及组] 开心的金明(Happy Jinming) 题解

思路分析

标准 0/1 背包问题：将总钱数 $n$ 视为背包容量，第 $i$ 件物品的体积为价格 $v_i$，价值为 $v_i \times p_i$。使用一维滚动数组 dp[0..n]，对每件物品逆序枚举容量 j 从 n 到 v 更新 dp[j] = max(dp[j], dp[j - v] + v * p) 即可。时间复杂度 $O(nm)$。

参考代码

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

long long dp[30005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i)
    {
        int v, p;
        cin >> v >> p;
        long long val = 1LL * v * p;
        for (int j = n; j >= v; --j)
        {
            dp[j] = max(dp[j], dp[j - v] + val);
        }
    }
    cout << dp[n] << "\n";
    return 0;
}