桥渡难题

Question

四个人必须在晚上过桥.任何穿过一个或两个男人的派对都必须随身携带手电筒.手电筒必须来回走动; 它不能被抛出等等.每个人都以不同的速度行走.一分钟需要1分钟,另外2分钟,另外5分钟,最后10分钟.如果两个男人交叉在一起,他们必须以较慢的男人的步伐走路.没有技巧 - 男人都是从同一侧开始,手电筒不能长距离照射,没有人可以携带,等等.

问题是他们能够最快地获得的是什么.我基本上是在寻找一些针对这类问题的通用方法.我的朋友告诉我,这可以通过Fibonacci系列解决,但解决方案并不适用于所有人.

请注意,这不是家庭作业.

Answer 1

有一整个PDF(备用链接)可以解决此问题的一般情况(在正式证明中).

Answer 2

17分钟 - 这是一个经典的MS问题.

1,2 => 2 minutes passed.
1 retuns => 3 minutes passed.
5,10 => 13 minutes passed.
2 returns => 15 minutes passed.
1,2 => 17 minute passed.

一般来说,最大的问题/最慢的人应该总是放在一起,并且最快的足够的旅行每次都能够在不使用慢速资源的情况下带回光.

Answer 3

我会通过在Dice.com上放置一个假工作广告解决这个问题,然后在面试中问这个问题,直到有人做对了.

Answer 4

As per Wikipedia

The puzzle is known to have appeared as early as 1981, in the book Super Strategies For Puzzles and Games. In this version of the puzzle, A, B, C and D take 5, 10, 20, and 25 minutes, respectively, to cross, and the time limit is 60 minutes

This question was however popularized after its appearance in the book "How Would You Move Mount Fuji?"

the question can be generalized for N people with varying individual time taken to cross the bridge.

The below program works for a generic N no of people and their times.

class Program
{
    public static int TotalTime(List<int> band, int n)
    {
        if (n < 3)
        {
            return band[n - 1];
        }
        else if (n == 3)
        {
            return band[0] + band[1] + band[2];
        }
        else
        {
            int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0];
            int temp2 = band[1] + band[0] + band[n - 1] + band[1];

            if (temp1 < temp2)
            {
                return temp1 + TotalTime(band, n - 2);
            }
            else if (temp2 < temp1)
            {
                return temp2 + TotalTime(band, n - 2);
            }
            else
            {
                return temp2 + TotalTime(band, n - 2);
            }
        }
    }

    static void Main(string[] args)
    {
        // change the no of people crossing the bridge
        // add or remove corresponding time to the list
        int n = 4; 

        List<int> band = new List<int>() { 1, 2, 5, 10 };

        band.Sort();

        Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n));
        Console.ReadLine();
    }
}

OUTPUT:

The total time taken to cross the bridge is: 17

For,

int n = 5; 
List<int> band = new List<int>() { 1, 2, 5, 10, 12 };

OUTPUT:

The total time taken to cross the bridge is: 25

For,

int n = 4; 
List<int> band = new List<int>() { 5, 10, 20, 25 };

OUTPUT The total time taken to cross the bridge is: 60