POJ 2923 - Relocation

http://poj.org/problem?id=2923

概要

\(n\) 個の家具を2台の車で運ぶ。 各家具の重さは \(w_i\) であり、車はそれぞれ合計 \(C_1, C_2\) の重さまで積むことができる。

このとき、最小で何回ですべての家具を運び出せるかを答える。

制約

解法

ある家具をどちらの車で運ぶかを決めれば、貪欲に積むのが最適になる。 \(n\) が小さいので \(2 ^ n\) 通り全探索してチェックしても間に合う。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 static const int INF = 10000;
 6 
 7 int f(vector<int>& v, int C)
 8 {
 9   int c = 0;
10   while (!v.empty()) {
11     if (v[0] > C) {
12       return INF;
13     }
14     int r = C;
15     for (vector<int>::iterator it = v.begin(); it != v.end();) {
16       if (*it <= r) {
17         r -= *it;
18         it = v.erase(it);
19       } else {
20         ++it;
21       }
22     }
23     ++c;
24   }
25   return c;
26 }
27 
28 int main()
29 {
30   int T;
31   cin >> T;
32   for (int Ti = 1; Ti <= T; Ti++) {
33     int N, C1, C2;
34     cin >> N >> C1 >> C2;
35     vector<int> v(N);
36     for (int i = 0; i < N; i++) {
37       cin >> v[i];
38     }
39     sort(v.rbegin(), v.rend());
40 
41     int ans = INF;
42     for (unsigned s = 0; s < (1U<<N); s++) {
43       vector<int> w[2];
44       for (int i = 0; i < N; i++) {
45         w[!(s & (1<<i))].push_back(v[i]);
46       }
47       ans = min(ans, max(f(w[0], C1), f(w[1], C2)));
48     }
49     cout << "Scenario #" << Ti << ":" << endl;
50     cout << ans << endl << endl;
51   }
52   return 0;
53 }
poj/2923.cc