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.
Each time you receive a piece of data, declare Map1. Then iterate over the loop for(auto mm:Map1), and declare two variables, newMoney and newPrice. The values of the two variables are "mm.first + received money" and "mm.second + (received money * importance)". If newMoney > N, it means that the budget has been exceeded, so continue directly. Otherwise, check if the old Map[newMoney] is less than newPrice. If newPrice is larger, set Map[newMoney] to newPrice. Each time check the maximum value of newPrice, and the answer is its maximum value.
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";
}