/*--------------------------------------------- * 日期:2015-03-02 * 作者:SJF0115 * 题目: 选择原料工厂(最短距离问题) * 来源:经典面试题 * 博客: -----------------------------------------------*/ #include <iostream> #include <algorithm> #include <climits> #include <vector> #include <math.h> using namespace std; int fac[100][100]; // n工厂个数 count原料厂个数 result原料厂下标集合 vector<int> BestFactoryPoint(int n,int count){ vector<int> result; //[1,n] int k; for(int i = 1;i <= n;){ //[1,n]分成两部分[1,k]有count-1个原料厂[k+1,n]有1个原料厂 k = fac[n][count--]; // [k+1,n]有一个原料厂,中位点就是原料厂点 result.push_back(k+1 + (n-k-1)/2); // 所有原料厂寻找完毕 if(count == 0){ break; }//if // 如果工厂个数小于原料厂个数 // 所有工厂全是原料厂 if(k <= count){ for(int i = 1;i <= k;++i){ result.push_back(i); }//for break; }//if // 求[1,k]部分 n = k; }//for return result; } // 从[start,end]选择一点使其到其他点的距离最小 int MinDistanceOneFactory(int point[],int start,int end){ if(start > end){ return -1; }//if int mid = (start + end) / 2; // 计算距离 int distance = 0; for(int i = start;i <= end;++i){ distance += abs(point[i] - point[mid]); }//for return distance; } // int MinDistance(int point[],int n,int count){ if(n <= 0){ return -1; }//if // // B[i][j]表示从第i个工厂到第j个工厂设1个原料厂的最短距离 // i <= j B上三角有用 int B[n+1][n+1]; // 计算第i个工厂到第j个工厂设1个原料厂的最短距离 for(int i = 1;i <= n;++i){ for(int j = i;j <= n;++j){ B[i][j] = MinDistanceOneFactory(point,i,j); }//for }//for // A[i][j]表示从前i个工厂中设j个原料厂的最短距离之和 int A[n+1][n+1]; // i前i个工厂 for(int i = 1;i <= n;++i){ // 设j个原料厂 // j = 1时 A[i][1] = B[1][i]; for(int j = 2;j <= i;++j){ A[i][j] = INT_MAX; for(int k = j-1;k < i;++k){ int curMin = A[k][j-1] + B[k+1][i]; if(curMin < A[i][j]){ A[i][j] = curMin; fac[i][j] = k; }//if }//for }//for }//for return A[n][count]; } int main() { int array[] = {0, 0, 4, 5, 10, 12, 18, 27, 30, 31, 38, 39, 47}; int n = 12; int count = 3; cout<<"最小距离->"<<MinDistance(array,n,count)<<endl; vector<int> result = BestFactoryPoint(n,count); for(int i = result.size()-1;i >= 0;--i){ cout<<array[result[i]]<<" "; }//for cout<<endl; return 0; }
38,39,47必有一个,39到47和47到39的距离是固定的,所以只要减少38的距离,38离39最近,故,所有的点中必有39