一個規劃性問題
12個工廠分布在一條東西向高速公路的兩側，工廠距離公路最西端的距離分別是0、4、5、10、12、18、27、30、31、38、39、47.在這12個工廠中選取3個原料供應廠，使得剩余工廠到最近的原料供應廠距離之和最短，問應該選哪三個廠 ？
這是阿里云實習的筆試題
這個類似于電梯調度算法，電梯調度是一個點，這里是三個點。
最直觀的做法是枚舉所有的情況，P(12, 3)。
其實也就是這樣。三個 for 循環，但是這就是一種暴力的解法。
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5 int min3(int a, int b, int c)
6 {
7 a = a < b ? a : b;
8 return a < c ? a : c;
9 }
10
11 int bar(int a[], int n, int x, int y, int z)
12 {
13 int ret = 0;
14 for (int i = 0; i != n; ++i)
15 {
16 ret += min3(abs(a[x] - a[i]), abs(a[y] - a[i]), abs(a[z] - a[i]));
17 }
18 return ret;
19 }
20
21 int foo(int a[], int n, int& p1, int& p2, int& p3)
22 {
23 int ret = 10000;
24 int tmp = 0;
25 for (int i = 0; i != n; ++i)
26 {
27 for (int j = 0; j != n; ++j)
28 {
29 for (int k = 0; k != n; ++k)
30 {
31 tmp = bar(a, n, i, j, k);
32 if (tmp < ret)
33 {
34 ret = tmp;
35 p1 = i;
36 p2 = j;
37 p3 = k;
38 }
39 // cout << i << ' ' << j << ' ' << k << endl;
40 // cout << tmp << endl;
41 }
42 }
43 }
44 return ret;
45 }
46
47 int main()
48 {
49 int a[] = {0, 4, 5, 10, 12, 18, 27, 30, 31, 38, 39, 47};
50 int x, y, z;
51 int d;
52 d = foo(a, sizeof (a) / sizeof (*a), x, y, z);
53 cout << d << endl;
54 cout << x << ' ' << y << ' ' << z << endl;
55 return 0;
56 }
posted on 2011-07-26 11:43
unixfy 閱讀(378)
評論(0) 編輯 收藏 引用