同題：UVa 10664 – Luggage
Peter and his friends are on vacation, and they’ve decided to drive to northern Spain.
There are seven of them in total, and they believe two cars are enough to fit all their luggage.
It’s time to go! Time to hit the road.
However, the drivers have different opinions about which suitcase should go into which trunk because no one wants their car to carry more weight (as it increases fuel consumption).
How can the luggage be distributed so that both cars carry the same total weight?
(The drivers cannot split or repack any luggage!)
Each suitcase has a label M indicating its weight.
If possible, please help them distribute the luggage evenly between the two cars.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input’s first line contains an integer T, representing the number of test cases.
Each test case is provided on a separate line and consists of N integers (1 ≤ N ≤ 20). These integers represent the weight M of each suitcase (0 < M ≤ 200). | For each test case:
•If it is possible to distribute the luggage such that the total weight carried by the two cars is equal, output “YES”. •Otherwise, output “NO”. |
| 3 1 2 1 2 1 2 3 4 1 2 5 10 50 3 50 3 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1 | NO YES YES |
Thought Process
Use a string to receive the input data, split it into an array of integers, and follow these steps:
1. Calculate the total weight of all luggage.
2. If the total weight is odd, directly output “NO” (as it’s impossible to split it equally).
3. Otherwise, calculate half of the total weight, which is the target weight for one car.
• If one subset of luggage can achieve this target weight, output “YES” (since the other subset will automatically have the same weight).
• If not, output “NO”.
宣告一個 Map 來存哪些數字或是數字和出現過，將陣列中的數字一一跑過，裡面在跑一個迴圈從一半跑到目前的數字，是 –。如果 Map[目前數字 – 陣列數字] > 0，則將 Map[目前數字]++。最後也要將 Map[陣列數字]++。
如果 Map[一半] > 0，就代表可以平分，反之就是不行。
Sample Code－ZeroJudge E559: Luggage
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
cin.ignore();
for (int i = 0; i<T; i++) {
string str;
getline(cin, str);
string add = "";
vector<int>v;
int sum = 0;
for (int j = 0; j<str.length(); j++) {
const char ch = str[j];
if (ch == ' ') {
int toInt;
if (add.length() == 1) toInt = add[0] - '0';
else toInt = stoi(add);
sum += toInt;
v.push_back(toInt);
add = "";
continue;
}
add += ch;
}
if (add.length() > 0) {
int tmp;
if (add.length() == 1) tmp = add[0] - '0';
else tmp = stoi(add);
sum += tmp;
v.push_back(tmp);
}
if (sum % 2 != 0) cout << "NO\n";
else {
const int half = sum / 2;
unordered_map<int, int>MAP;
for (int i = 0; i<v.size(); i++) {
const int tmp = v[i];
for (int j = half; j>=tmp; j--) {
if (MAP[j-tmp] > 0) MAP[j]++;
}
MAP[tmp]++;
}
if (MAP[half] > 0) cout << "YES\n";
else cout << "NO\n";
}
}
}
//ZeroJudge E559
//Dr. SeanXD