首页 > 试题广场 >

12个工厂分布在一条东西向高速公路的两侧,工厂距离公路最西端

[单选题]
12个工厂分布在一条东西向高速公路的两侧,工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47。在这12个工厂中选取3个原料供应厂,使得剩余工厂到最近的原料供应厂距离之和最短,问应该选哪三个厂 ? 
  • 5,4,10
  • 27,4,10
  • 0,4,10
  • 5,27,39
发表于 2016-04-06 20:41:17 回复(4)
答案:D
思路:这道题在开始就诱导人们想两侧,其实不然,我们把工厂位置看成一条线,在里面找3个点, 剩余的工厂到最近的点的距离要尽量地小,那我们这3个点就要尽量分开,可以当成是上面一个,中间一个,下面一个,那这三个点之间必然要间隔这几个工厂,我们再看回选择部分,A选项4和5太近,是不可能的了,B选项的7有点莫名其妙,因为没有这个工厂。C选项的0和4也是相隔太近了。最后自然剩下D了
发表于 2014-12-30 18:49:40 回复(5)
(1)工厂距离是从小到大排序的。
(2)从N个工厂中选择1个原料厂,选择位于中位数位置的工厂,距离之和最短。
(3)设A[i][j]表示从前i个工厂选择j个原料厂的最短距离 (1<=i<=j<=N)
B[i][j]表示从第i个工厂到第j个工厂选择1个原料厂的最短距离。(1<=j<=i<=N)
(4)从前i个工厂选择j个原料厂,可分为两部分:
从前k个工厂选择j-1个原料厂和从第k+1个工厂到第i个工厂选择1个原料厂(1<=j-1<=k<i, k+1<=i)
若j-1等于0, 则前k个工厂没有原料厂了。
(5)递归解为:
A[i][j] = B[1][i], 即j=1时
A[i][j] = min{ A[k][j-1] + B[k+1][i] },其中1<=j-1<=k<i, k+1<=i

代码
    /*---------------------------------------------
    *   日期: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;
    }

得到答案:5 27 39




编辑于 2015-03-02 11:05:08 回复(10)
呃呃呃,大家好复杂,我蒙了一个   12个厂距离平均数,然后乘以3。再选出哪三个之和接近就是了
发表于 2021-11-29 21:14:33 回复(0)
解题思路:蒙!
发表于 2018-07-17 15:23:21 回复(0)
选择题快速分析:俩俩之间距离最大为9、8、7、6,因此后面31 38 39 47必然有一个供应,明显是39,所以选D 笔试题:由于具有最优子结构,还可以拆分为最小子问题,因此可以动态规划求解。设d(i, C)表示前i个有C个供应厂的最短距离,此时形式基本与背包问题相同,C和i都从1开始逐渐增加,即可列出结果矩阵
发表于 2018-02-25 14:17:55 回复(0)
我惊了,大家的代码方法和思路对我来说有点难。我直接使用先排除极端值A,C,再使用代入法比较B和D。
发表于 2022-03-20 10:35:37 回复(1)
这题…真行
发表于 2022-09-12 20:38:48 回复(0)

38,39,47必有一个,39到47和47到39的距离是固定的,所以只要减少38的距离,38离39最近,故,所有的点中必有39

发表于 2021-03-13 21:34:06 回复(0)
直接瞎蒙。。。
发表于 2020-03-28 14:55:07 回复(0)
排序算法
发表于 2016-08-30 11:06:49 回复(0)