AOJ 2296 - Quest of Marchant

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2296

解法

買い物に行く街の部分集合 X は 2^N 個程度． X に含まれる街を巡って市場へ帰ってくるときの最短距離は全通り試して調べても |X|! で求められる．

X で買える商品を，合計の重さが W 以下になるようにしつつ利益が最大になるように買ったときの利益は，いわゆるナップザック問題なので DP で解ける．

最後に，合計の時間が T 以下になるようにしつつ利益が最大になるように買ったときの利益を，同様の DP で解く．

全体で O(2^N*(N! + M*W) + 2^N*T)．

int の範囲に収まらない可能性がある点に注意．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct town
 8 {
 9   int x, y;
10   vector<pair<int,int> > items;
11 };
12 
13 inline int manhattan(const pair<int,int>& p, const pair<int,int>& q)
14 {
15   return abs(p.first - q.first) + abs(p.second - q.second);
16 }
17 
18 int main()
19 {
20   int N, M, W, T;
21   cin >> N >> M >> W >> T;
22   map<string, int> weight, market_price;
23   for (int i = 0; i < M; i++) {
24     string s;
25     int v, p;
26     cin >> s >> v >> p;
27     weight.insert(make_pair(s, v));
28     market_price.insert(make_pair(s, p));
29   }
30 
31   vector<town> towns;
32   for (int i = 0; i < N; i++) {
33     town t;
34     int L;
35     cin >> L >> t.x >> t.y;
36     for (int j = 0; j < L; j++) {
37       string r;
38       int q;
39       cin >> r >> q;
40       t.items.push_back(make_pair(weight[r], market_price[r] - q));
41     }
42     towns.push_back(t);
43   }
44 
45   vector<pair<int,long long> > routes;
46   for (int s = 1; s < (1<<N); s++) {
47     vector<pair<int,int> > posses, items;
48     for (int i = 0; i < N; i++) {
49       if (s & (1<<i)) {
50         posses.push_back(make_pair(towns[i].x, towns[i].y));
51         for (vector<pair<int,int> >::const_iterator it = towns[i].items.begin(); it != towns[i].items.end(); ++it) {
52           items.push_back(*it);
53         }
54       }
55     }
56 
57     // minimum time (tsp)
58     int t = 10000000;
59     sort(posses.begin(), posses.end());
60     do {
61       int d = 0;
62       d += manhattan(make_pair(0, 0), posses.front());
63       for (vector<pair<int,int> >::const_iterator it = posses.begin(); it+1 != posses.end(); ++it) {
64         d += manhattan(*it, *(it+1));
65       }
66       d += manhattan(posses.back(), make_pair(0, 0));
67       t = min(t, d);
68     } while (next_permutation(posses.begin(), posses.end()));
69 
70     // maximum profit (knapsack)
71     vector<long long> dp(W+1, 0LL);
72     long long prof = 0LL;
73     for (vector<pair<int,int> >::const_iterator it = items.begin(); it != items.end(); ++it) {
74       for (int i = 0; i + it->first <= W; i++) {
75         dp[i + it->first] = max(dp[i + it->first], dp[i] + it->second);
76         prof = max(prof, dp[i + it->first]);
77       }
78     }
79     routes.push_back(make_pair(t, prof));
80   }
81 
82   // maximum profit (knapsack)
83   vector<long long> dp(T+1, 0LL);
84   long long ans = 0LL;
85   for (vector<pair<int,long long> >::const_iterator it = routes.begin(); it != routes.end(); ++it) {
86     for (int i = 0; i + it->first <= T; i++) {
87       dp[i + it->first] = max(dp[i + it->first], dp[i] + it->second);
88       ans = max(ans, dp[i + it->first]);
89     }
90   }
91   cout << ans << endl;
92   return 0;
93 }