ZeroJudge B131: 開心的金明

金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分為 5 等：用整數 1～5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格 (都是整數元）。他希望在不超過 N 元 (可以等於 N 元) 的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第 j 件物品的價格為 v[j]，重要度為 w[j]，共選中了 k 件物品，編號依次為 j₁、j₂、……、j_k，則所求的總和為：

(v[j1]＊w[j1]) + (v[j2]＊w[j2]) + … + (v[jk]＊w[jk])。

請你幫助金明設計一個滿足要求的購物單。

範例測資

解題思路

宣告一個 Map 代表不同價錢可以獲得的最大值，然後宣告另外一個 Map (這邊叫 Map1) 來做新資料的計算，算完再把資料存到 Map 中。

每次收到一個資料時都宣告 Map1，然後跑 for(auto mm:Map1) 的迴圈，並且宣告兩個變數分別為 newMoney 和 newPrice，兩個變數的值分別為「mm.first + 收到的錢」以及「mm.second + (收到的錢＊重要度)」。如果 newMoney > N，代表已經超過預算，直接 continue，否則就判斷舊的 Map[newMoney] 是否 < newPrice，如果 newPrice 較大則將 Map[newMoney] 設為 newPrice，然後每次判斷 newPrice 最大值，答案就是其最大值。

範例程式碼－ZeroJudge B131: 開心的金明

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    map<int, int>MAP;
    MAP[0] = 0;
    int ans = -1;
    for (int i = 0; i<M; i++) {
        int money, vital;
        cin >> money >> vital;
        map<int,int> MAP1 = MAP;
        const int calc = money * vital;
        for(auto mm:MAP1) {
            int newMoney = mm.first + money;
            int newPrice = mm.second + calc;
            if(newMoney > N) continue;
            if(MAP1[newMoney] < newPrice) {
                MAP[newMoney] = newPrice;
                ans = max(ans, newPrice);
            }
        }
    }
    cout << ans << "\n";
}