Jinming is very happy today because he's about to receive the keys to his new house, which includes a spacious room just for him. What's more, his mother told him yesterday, "You can decide what items to purchase for your room and how to decorate it. Just make sure not to exceed $N." Early in the morning, Jinming started budgeting. However, he wants to buy too many things, which will surely exceed his mother's limit of $N. So, he assigned an importance level to each item, ranging from 1 to 5 (where 5 is the most important). He also found out the prices of each item on the internet (all prices are integers in $). He hopes to maximize the sum of the products of each item's price and importance level, without exceeding $N (it can be exactly $N).
Given that the price of the j-th item is v[j] and its importance is w[j], and a total of k items are selected with indices j1, j2, …, jk, the total sum sought is:
(v[j1]＊w[j1]) + (v[j2]＊w[j2]) + … + (v[jk]＊w[jk])
Please help Jinming design a shopping list that meets the requirements.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| For each set of inputs, the first line consists of two positive integers, N and M, separated by a space: (Where N < 30000 represents the total amount of money available, and M < 25 indicates the number of items Jinming wishes to purchase.) From the 2nd line to the M+1th line, each line provides basic data for an item indexed from 0 to M−1. Each line contains 2 non-negative integers, V and P. (Where V represents the price of the item V ≤ 10000, and P represents the importance level of the item, ranging from 1 to 5.) | For each set of inputs, the output consists of a single positive integer. This integer represents the maximum sum of the products of prices and importance levels of items that do not exceed the total amount of money available, and it is guaranteed to be less than 100,000,000. |
| 1000 5 800 2 400 5 300 5 400 3 200 2 | 3900 |
Thought Process
Declare a Map to represent the maximum values achievable for different prices. Then declare another Map (referred to as Map1 here) to perform calculations with new data, and after computing, store the data back into Map.
每次收到一個資料時都宣告 Map1，然後跑 for(auto mm:Map1) 的迴圈，並且宣告兩個變數分別為 newMoney 和 newPrice，兩個變數的值分別為「mm.first + 收到的錢」以及「mm.second + (收到的錢＊重要度)」。如果 newMoney > N，代表已經超過預算，直接 continue，否則就判斷舊的 Map[newMoney] 是否 < newPrice，如果 newPrice 較大則將 Map[newMoney] 設為 newPrice，然後每次判斷 newPrice 最大值，答案就是其最大值。
Sample Code－ZeroJudge B131: Bedroom Items
#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";
}