本文出自：

过桥问题解释：一条船能够坐两个人，可是有非常多人要过河，所以送过一个人去，还有一个人还要回来接。使全部人过河之后时间最短，怎样求？

此问题曾作为阿里巴巴题目

初看此题想的太过简单，直接让跑的最快的送过去，自己再跑回来就可以。事实上不然。

函数g(a,b)表示过河，b(a)表示回来。假设过河时间分别为1，2，5，10

那么两种过河方案：

1.初想方案：

    g（1，2）=2

    g (1, 10) = 10

    g (1, 5 ) =  5

    b(1) * 2 = 2

    sum  =19

2.还有一种方案：. g(1,2) =2

    b(1) =1

    g(5,10)=10

    b(2)=2

    g(1,2)=2

    sum = 17

还有一种方案就是让两个跑的快的先跑过去，然后一个带回来船，然后两个慢的跑过去，还有一个跑的快的带回来船。

如此两种方案的速度分别为：

设跑的快的分别为a, b,跑的慢的为c, d

那么c, d过河须要的时间分别为：

1.a + a + c + d

2.a +ｂ＋ｂ＋ｄ

如此一来，求得ｂ＋ｂ与ａ＋ｃ的大小关系，则知道取哪种方案最佳。

题目有poj2573, poj1700

1700解题代码：（也有dfs，dp写法，可是我没理解）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int main(){    int n, sec;    int time[1010];    int t;    int temp;    int i, j, k;    //freopen("test", "r", stdin);    scanf("%d", &t);    while(t--)    {        scanf("%d", &n);        memset(time, 0, sizeof(time));                for(i = 0; i < n; i++)            scanf("%d", &time[i]);        if(n == 1)            printf("%d\n", time[0]);                else if(2 == n)            printf("%d\n", time[0] > time[1] ? time[0] : time[1]);                else if(3 == n)            printf("%d\n", time[0] + time[1] + time[2]);                else        {            sec = 0;            sort(time ,time + n);            temp = time[1]*2;                        while(n >=4)            {                sec += time[0];                sec += time[n-1];                i = time[1] * 2;                j = time[0] + time[n-2];                if(i > j)                    sec += j;                else                     sec += i;                n -= 2;            }            if(2 == n)                printf("%d\n", sec + time[1]);                    else if(3 == n)                printf("%d\n", sec + time[0] + time[1] + time[2]);        }    }        return 0;}
        
       
      
     

2573：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;struct outPut{    int front, end;    outPut(int a, int b):front(a), end(b){}    outPut(int a):front(a), end(-1){}};void output(outPut *a){    if(a->end != -1)        printf("%d %d\n", a->front, a->end);    else        printf("%d\n", a->front);}int main(){    int temp;    int pe[1010];    int i, j;    int n;    // cost time    int sec;    //freopen("test", "r", stdin);    queue 
          
 Queue; while(~scanf("%d", &n)) { //printf("\nCase: \n"); for(i = 0; i < n; i++) scanf("%d", &pe[i]); if(1 == n) { printf("%d\n", pe[0]); printf("%d\n", pe[0]); } //.. else if(2 == n) { if(pe[0] > pe[1]) { i = pe[0]; j = pe[1]; } else { i = pe[1]; j = pe[0]; } printf("%d\n", i); printf("%d %d\n", j, i); } else if(3 == n) { sort(pe, pe+3); printf("%d\n", pe[0]+pe[1]+pe[2]); printf("%d %d\n", pe[0], pe[2]); printf("%d\n", pe[0]); printf("%d %d\n", pe[0], pe[1]); } else { sort(pe, pe+n); temp = pe[1] * 2; sec = 0; while(n >= 4) { sec += pe[n-1]; sec += pe[0]; if(temp < pe[0] + pe[n-2]) { Queue.push(outPut(pe[0], pe[1])); Queue.push(outPut(pe[0])); Queue.push(outPut(pe[n-2], pe[n-1])); Queue.push(outPut(pe[1])); sec += temp; } else { Queue.push(outPut(pe[0], pe[n-1])); Queue.push(outPut(pe[0])); Queue.push(outPut(pe[0], pe[n-2])); Queue.push(outPut(pe[0])); sec += pe[0] + pe[n-2]; } n -= 2; } if(2 == n) { outPut *tmp; printf("%d\n", sec + pe[1]); while(!Queue.empty()) { tmp = &Queue.front(); output(tmp); Queue.pop(); } printf("%d %d\n", pe[0], pe[1]); } else if(3 == n) { outPut *tmp; printf("%d\n", sec + pe[0] + pe[1] + pe[2]); while(!Queue.empty()) { tmp = &Queue.front(); output(tmp); Queue.pop(); } printf("%d %d\n", pe[0], pe[2]); printf("%d\n", pe[0]); printf("%d %d\n", pe[0], pe[1]); } } } return 0;}