IT公司面试手册

现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1分，小明的弟弟要3分，小明的爸爸要6分，小明的妈妈要8分，小明的爷爷要12分。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短？（原本是个小小智力题，据说是外企的面试题，在这里用程序来求解）
#include “stdafx.h”
#define N    5
#define SIZE 64

// 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4
// 每个人的当前位置：0–在桥左边， 1–在桥右边
int Position[N];   
// 过桥临时方案的数组下标； 临时方案； 最小时间方案；
int Index, TmpScheme[SIZE], Scheme[SIZE];  
// 最小过桥时间总和，初始值100；每个人过桥所需要的时间
int MinTime=100, Time[N]={1, 3, 6, 8, 12}; 
// 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间;
// Direction:过桥方向,1–向右,0–向左
void Find(int Remnant, int CurTime, int Direction) {
    if(Remnant == 0) {                               // 所有人已经过桥，更新最少时间及方案
        MinTime=CurTime;
        for(int i=0; i<SIZE && TmpScheme[i]>=0; i++)
            Scheme[i] = TmpScheme[i];
    } else if(Direction == 1) {                        // 过桥方向向右，从桥左侧选出两人过桥
        for(int i=0; i<N; i++)                   
            if(Position[i] == 0 && CurTime + Time[i] < MinTime) {
                TmpScheme[Index++] = i;
                Position[i] = 1;
                for(int j=0; j<N; j++) {
                    int TmpMax = (Time[i] > Time[j] ? Time[i] : Time[j]);
                    if(Position[j] == 0 && CurTime + TmpMax < MinTime) {
                        TmpScheme[Index++] = j;   
                        Position[j] = 1;       
                        Find(Remnant – 2, CurTime + TmpMax, !Direction);
                        Position[j] = 0;       
                        TmpScheme[--Index] = -1;
                    }
                }
                Position[i] = 0;
                TmpScheme[--Index] = -1;
            }
    } else {        // 过桥方向向左，从桥右侧选出一个人回来送灯
        for(int j=0; j<N; j++) {
            if(Position[j] == 1 && CurTime+Time[j] < MinTime) {
                TmpScheme[Index++] = j;
                Position[j] = 0;
                Find(Remnant+1, CurTime+Time[j], !Direction);
                Position[j] = 1;
                TmpScheme[--Index] = -1;
            }
        }
    }
}
int main(int argc, char* argv[]) {
    for(int i=0; i<SIZE; i++)   // 初始方案内容为负值，避免和人员标号冲突
        Scheme[i] = TmpScheme[i] = -1;

Find(N, 0, 1);        // 查找最佳方案

    printf(“MinTime=%d:”, MinTime); // 输出最佳方案
    for(int i=0; i<SIZE && Scheme[i]>=0; i+=3)
        printf(“  %d-%d  %d”, Scheme[i], Scheme[i+1], Scheme[i+2]);
    printf(“\b\b  “);
}