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.
一般来说，最大的问题/最慢的人应该总是放在一起，并且足够多的最快的旅行每次都能在不使用慢资源的情况下把光带回来。
我会通过在 Dice.com 上发布虚假招聘广告来解决这个问题，然后在面试中提出这个问题，直到有人答对为止。
根据维基百科
众所周知，这个谜题早在 1981 年就出现在《谜题和游戏的超级策略》一书中。在这个版本的拼图中，A、B、C、D 分别需要 5、10、20 和 25 分钟穿越，时间限制为 60 分钟
然而，这个问题在出现在《你将如何移动富士山？
这个问题可以概括为 N 个人过桥所花费的个人时间不同。
以下程序适用于一般 N 人及其时间。
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();
}
}
输出：
过桥的总时间是：17
为了，
int n = 5;
List<int> band = new List<int>() { 1, 2, 5, 10, 12 };
输出：
过桥的总时间是：25
为了，
int n = 4;
List<int> band = new List<int>() { 5, 10, 20, 25 };
OUTPUT 过桥的总时间是：60
这是 ruby 中的响应：
@values = [1, 2, 5, 10]
# @values = [1, 2, 5, 10, 20, 25, 30, 35, 40]
@values.sort!
@position = @values.map { |v| :first }
@total = 0
def send_people(first, second)
first_time = @values[first]
second_time = @values[second]
@position[first] = :second
@position[second] = :second
p "crossing #{first_time} and #{second_time}"
first_time > second_time ? first_time : second_time
end
def send_lowest
value = nil
@values.each_with_index do |v, i|
if @position[i] == :second
value = v
@position[i] = :first
break
end
end
p "return #{value}"
return value
end
def highest_two
first = nil
second = nil
first_arr = @position - [:second]
if (first_arr.length % 2) == 0
@values.each_with_index do |v, i|
if @position[i] == :first
first = i unless first
second = i if !second && i != first
end
break if first && second
end
else
@values.reverse.each_with_index do |v, i|
real_index = @values.length - i - 1
if @position[real_index] == :first
first = real_index unless first
second = real_index if !second && real_index != first
end
break if first && second
end
end
return first, second
end
#we first send the first two
@total += send_people(0, 1)
#then we get the lowest one from there
@total += send_lowest
#we loop through the rest with highest 2 always being sent
while @position.include?(:first)
first, second = highest_two
@total += send_people(first, second)
@total += send_lowest if @position.include?(:first)
end
p "Total time: #{@total}"
另一个受@roc-khalil 解决方案启发的 Ruby 实现
@values = [1,2,5,10]
# @values = [1,2,5,10,20,25]
@left = @values.sort
@right = []
@total_time = 0
def trace(moving)
puts moving
puts "State: #{@left} #{@right}"
puts "Time: #{@total_time}"
puts "-------------------------"
end
# move right the fastest two
def move_fastest_right!
fastest_two = @left.shift(2)
@right = @right + fastest_two
@right = @right.sort
@total_time += fastest_two.max
trace "Moving right: #{fastest_two}"
end
# move left the fastest runner
def move_fastest_left!
fastest_one = @right.shift
@left << fastest_one
@left.sort!
@total_time += fastest_one
trace "Moving left: #{fastest_one}"
end
# move right the slowest two
def move_slowest_right!
slowest_two = @left.pop(2)
@right = @right + slowest_two
@right = @right.sort
@total_time += slowest_two.max
trace "Moving right: #{slowest_two}"
end
def iterate!
move_fastest_right!
return if @left.length == 0
move_fastest_left!
move_slowest_right!
return if @left.length == 0
move_fastest_left!
end
puts "State: #{@left} #{@right}"
puts "-------------------------"
while @left.length > 0
iterate!
end
输出：
State: [1, 2, 5, 10] []
-------------------------
Moving right: [1, 2]
State: [5, 10] [1, 2]
Time: 2
-------------------------
Moving left: 1
State: [1, 5, 10] [2]
Time: 3
-------------------------
Moving right: [5, 10]
State: [1] [2, 5, 10]
Time: 13
-------------------------
Moving left: 2
State: [1, 2] [5, 10]
Time: 15
-------------------------
Moving right: [1, 2]
State: [] [1, 2, 5, 10]
Time: 17
-------------------------
如此小的问题空间，对所有可能性的详尽搜索很简单。广度或深度优先会起作用。这是一个简单的CS问题。
我自己更喜欢传教士和食人族的问题
17 - 一个非常常见的问题
-> 1-2 = 2
<- 2 = 2
-> 5,10 = 10（没有一个必须返回）
<- 1 = 1
-> 1,2 = 2
另一边的所有
总数 = 2+2+10+1+2 = 17
通常人们在第一次尝试时会得到 19
考虑到将有 2 条边，第 1 边和第 2 边，N 个人应该从第 1 边到第 2 边过桥。通过限制 L 人过桥的逻辑是 -
第 1 步：将 L 个最快的成员从第 1 侧移动到第 2 侧
第 2 步：将最快的人从第 2 侧带回第 1 侧
第 3 步：将 L 个最慢的成员从第 1 侧移动到第 2 侧
第 4 步：带回 Side 2 中最快的人
重复这些步骤，直到在第 2 步结束时或在第 4 步结束时，您将在第 1 面中没有人。
此处为 n 人的 C# 代码，一次只有 2 人。这将吸收 N 人，可以在运行时指定。然后它将接受 N 个人的人名和所用时间。输出还指定了可能的最短时间的迭代。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RiverCrossing_Problem
{
class Program
{
static void Main(string[] args)
{
Dictionary<string, int> Side1 = new Dictionary<string, int>();
Dictionary<string, int> Side2 = new Dictionary<string, int>();
Console.WriteLine("Enter number of persons");
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter the name and time taken by each");
for(int a =0; a<n; a++)
{
string tempname = Console.ReadLine();
int temptime = Convert.ToInt32(Console.ReadLine());
Side1.Add(tempname, temptime);
}
Console.WriteLine("Shortest time and logic:");
int totaltime = 0;
int i = 1;
do
{
KeyValuePair<string, int> low1, low2, high1, high2;
if (i % 2 == 1)
{
LowestTwo(Side1, out low1, out low2);
Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", low1.Key, low2.Key, low2.Value);
Side1.Remove(low2.Key);
Side1.Remove(low1.Key);
Side2.Add(low2.Key, low2.Value);
Side2.Add(low1.Key, low1.Value);
totaltime += low2.Value;
low1 = LowestOne(Side2);
Console.WriteLine("{0} comes back to side 1, time taken = {1}", low1.Key, low1.Value);
totaltime += low1.Value;
Side1.Add(low1.Key, low1.Value);
Side2.Remove(low1.Key);
i++;
}
else
{
HighestTwo(Side1, out high1, out high2);
Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", high1.Key, high2.Key, high1.Value);
Side1.Remove(high1.Key);
Side1.Remove(high2.Key);
Side2.Add(high1.Key, high1.Value);
Side2.Add(high2.Key, high2.Value);
totaltime += high1.Value;
low1 = LowestOne(Side2);
Console.WriteLine("{0} comes back to side 1, time taken = {1}", low1.Key, low1.Value);
Side2.Remove(low1.Key);
Side1.Add(low1.Key, low1.Value);
totaltime += low1.Value;
i++;
}
} while (Side1.Count > 2);
KeyValuePair<string, int> low3, low4;
LowestTwo(Side1, out low3, out low4);
Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", low3.Key, low4.Key, low4.Value);
Side2.Add(low4.Key, low4.Value);
Side2.Add(low3.Key, low3.Value);
totaltime += low4.Value;
Console.WriteLine("\n");
Console.WriteLine("Total Time taken = {0}", totaltime);
}
public static void LowestTwo(Dictionary<string, int> a, out KeyValuePair<string, int> low1, out KeyValuePair<string, int> low2)
{
Dictionary<string, int> b = a;
low1 = b.OrderBy(kvp => kvp.Value).First();
b.Remove(low1.Key);
low2 = b.OrderBy(kvp => kvp.Value).First();
}
public static void HighestTwo(Dictionary<string,int> a, out KeyValuePair<string,int> high1, out KeyValuePair<string,int> high2)
{
Dictionary<string, int> b = a;
high1 = b.OrderByDescending(k => k.Value).First();
b.Remove(high1.Key);
high2 = b.OrderByDescending(k => k.Value).First();
}
public static KeyValuePair<string, int> LowestOne(Dictionary<string,int> a)
{
Dictionary<string, int> b = a;
return b.OrderBy(k => k.Value).First();
}
}
}
提供的随机输入的样本输出，在这种情况下为 7，一次有 2 个人通过将是：
Enter number of persons
7
Enter the name and time taken by each
A
2
B
5
C
3
D
7
E
9
F
4
G
6
Shortest time and logic:
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
E and D goes from side 1 to side 2, time taken = 9
C comes back to side 1, time taken = 3
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
G and B goes from side 1 to side 2, time taken = 6
C comes back to side 1, time taken = 3
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
A and F goes from side 1 to side 2, time taken = 4
Total Time taken = 40
我以代数方式列出了可能的解决方案，并以最快的时间得出了答案。并用 A、B、C、D 列表分配代数，其中 A 最小，D 最大，最短时间的公式是 B+A+D+B+B 或 3B+A+D 或用冗长的术语，第二快的时间之和 3 并与最快和最慢相加。
看节目也有增加项目的问题。虽然我还没有经历过，但我猜这个公式仍然适用，只需添加直到所有项目的第二个项目乘以 3 和除第二个最慢时间之外的所有项目的总和。例如，因为 4 个项目是 3 x 第二个 + 第一个和第四个。那么 5 个项目是 3 x 第二 + 第一、第三和第五。想用这个程序检查一下。
我也只是查看了上面共享的 pdf，所以对于更多项目，它是 3 x 秒 + 最快 + 最慢每对后续对的总和。
查看优化解决方案的步骤，这个想法是 - 右 - 对于向右移动的两个项目，最快的是第一和第二快， - 左 - 然后加上单个项目的最快返回是最快的项目 - 右 -带上最慢的 2 个项目，这将只考虑最慢的项目，而忽略第二个最慢的项目。-左 - 第二快的项目。-最后的权利 - 又是第一和第二快的
所以再次总结=第二快的3次，最快的一次，最慢的第二慢。
一个简单的算法是：假设'N'是可以同时穿越的人数，一个人必须背着火炬穿越
这是执行此操作的示例 python 脚本：https ://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py