一个规划性问题
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 阅读(350)
评论(0) 编辑 收藏 引用