POJ1040 Transportation
题目来源：http://poj.org/problem?id=1040
题目大意：
某运输公司要做一个测试。从A城市到B城市的一条运输线路中有若干个站，将所有站包括A和B在内按顺序编号为0到m。该路线上的一趟列车，乘客最大容量为cap。车开出之前，该趟车会收到来自各个车站的车票订单请求。一个请求包括起点站编号，终点站编号和乘客人数。每张车票的价格为起点到终点之间相隔的站数。在不超载的情况下，求一趟列车能获得的最大收益。对于某一个订单请求，要么接受要么拒绝，不能只接受其中的一部分乘客。
输入：每个测试用例一个数据块。每块的第一行有3个整数：cap:(车的容量), m:(终点城市的编号, 最大为7)，n:(订单数，最大为22).接下来的n行每行三个数表示一个订单，三个数分别为起点、终点、人数。
输出：没个测试用例单独一行，输出一个整数表示该趟列车能获得的最大收益。
Sample Input
10 3 4 0 2 1 1 3 5 1 2 7 2 3 10 10 5 4 3 5 10 2 4 9 0 2 5 2 5 8 0 0 0
Sample Output
19 34
由于数据量不算太大，直接用搜索就可以解决。搜索前先对所有订单按起点的顺序进行排序。
不加剪枝的dfs代码，耗时391ms：
1 ////////////////////////////////////////////////////////////////////////// 2 // POJ1040 Transportation 3 // Memory: 264K Time: 391MS 4 // Language: C++ Result: Accepted 5 ////////////////////////////////////////////////////////////////////////// 6 7 #include <iostream> 8 #include <algorithm> 9 10 using namespace std; 11 12 int n, m, cap; 13 14 class Order { 15 public: 16 int start; 17 int destination; 18 int cnt; 19 }; 20 21 Order orders[22]; 22 int maxE; 23 //记录每站有多少个乘客 24 int pasCnt[8]; 25 26 //比较函数，按start升序，destination降序，cnt降序 27 bool cmp(const Order &a, const Order &b) { 28 return a.start == b.start 29 ? (a.destination == b.destination ? (b.cnt < a.cnt) : b.destination < a.destination) 30 : a.start < b.start; 31 } 32 33 void dfs(int i, int now) { 34 if (now > maxE) { 35 maxE = now; 36 } 37 for (int t = i; t < n; ++t) { 38 if (pasCnt[orders[t].start] + orders[t].cnt > cap) continue;//reject 39 for (int j = orders[t].start; j < orders[t].destination; ++j) 40 //get in 41 pasCnt[j] += orders[t].cnt; 42 dfs(t + 1, now + orders[t].cnt * (orders[t].destination - orders[t].start)); 43 for (int j = orders[t].start; j < orders[t].destination; ++j) 44 pasCnt[j] -= orders[t].cnt; 45 } 46 } 47 48 int main(void) { 49 while (true) { 50 cin >> cap >> m >> n; 51 if (cap == 0 && m == 0 && n == 0) break; 52 for (int i = 0; i < n; ++i) 53 cin >> orders[i].start >> orders[i].destination >> orders[i].cnt; 54 //按起点顺序将订单排序 55 sort(orders, orders + n, cmp); 56 maxE = 0; 57 memset(pasCnt, 0, sizeof(pasCnt)); 58 dfs(0, 0); 59 cout << maxE << endl; 60 } 61 system("pause"); 62 return 0; 63 }
看了别人剪枝的方法，加上之后，时间瞬间降到16ms.
剪枝方法如下：
每一个order添加两个项v和r。v表示该张订单的收益值。r表示如果选择该选项最多还能获得多少收益，这个值只是一个上界而不是上确界。计算方法是，计算排序后该订单和排在该订单之后的所有订单的收益值之和。因为dfs是按订单顺序依次搜索的，所以当当前收益值加上该订单的r值小于等于已搜到的最大收益，则不必再考虑该订单及以后的订单，因为不可能再得到比已知最大收益更大的收益。
1 ////////////////////////////////////////////////////////////////////////// 2 // POJ1040 Transportation 3 // Memory: 236K Time: 16MS 4 // Language: C++ Result: Accepted 5 ////////////////////////////////////////////////////////////////////////// 6 7 #include <iostream> 8 #include <algorithm> 9 10 using namespace std; 11 12 int n, m, cap; 13 14 class Order { 15 public: 16 int start; 17 int destination; 18 int cnt; 19 int v; //该订单能获得的收益 20 int r; //选取该订单之后最多还能获得多少收益 21 }; 22 23 Order orders[22]; 24 int maxE; 25 //记录每站有多少个乘客 26 int pasCnt[8]; 27 28 //比较函数，按start升序，destination降序，cnt降序 29 bool cmp(const Order &a, const Order &b) { 30 return a.start == b.start 31 ? (a.destination == b.destination ? (b.cnt < a.cnt) : b.destination < a.destination) 32 : a.start < b.start; 33 } 34 35 void dfs(int i, int now) { 36 if (now > maxE) { 37 maxE = now; 38 } 39 for (int t = i; t < n; ++t) { 40 if (orders[t].r + now <= maxE) return; 41 if (pasCnt[orders[t].start] + orders[t].cnt > cap) continue;//reject 42 for (int j = orders[t].start; j < orders[t].destination; ++j) 43 //get in 44 pasCnt[j] += orders[t].cnt; 45 dfs(t + 1, now + orders[t].v); 46 for (int j = orders[t].start; j < orders[t].destination; ++j) 47 pasCnt[j] -= orders[t].cnt; 48 } 49 } 50 51 int main(void) { 52 while (true) { 53 cin >> cap >> m >> n; 54 if (cap == 0 && m == 0 && n == 0) break; 55 for (int i = 0; i < n; ++i) { 56 cin >> orders[i].start >> orders[i].destination >> orders[i].cnt; 57 orders[i].v = orders[i].cnt * (orders[i].destination - orders[i].start); 58 } 59 //按起点顺序将订单排序 60 sort(orders, orders + n, cmp); 61 for (int i = n - 1, sum = 0; i >= 0; --i) { 62 sum += orders[i].v; 63 orders[i].r = sum; 64 } 65 maxE = 0; 66 memset(pasCnt, 0, sizeof(pasCnt)); 67 dfs(0, 0); 68 cout << maxE << endl; 69 } 70 return 0; 71 }