最短时间过桥问题

附:增加源码下载地址-----------https://files.cnblogs.com/yeguo/Console.zip

问题如下：四个女人过桥，夜间有一火把，每次最多过两个，必需带火把，过桥速度不一样，分别为

no.1 1min
no.2 2min
no3 5min
no.4 10min

两个人过用最慢一个的速度，火把不能扔，如何在17min内四个女人都过桥？

这个问题其实园子里已经有解决方案了也讨论了多次不过呢很多只有思路源码也不够详细于是我再演绎一下归纳总结一下

其实是很简单的返回永远最多返回一个所以返回肯定是取已经过桥的人中时间最短的那一个

那么过桥呢过桥的话要么取时间最短的两个(最快速) 要么取最慢的两个(最不浪费快的那个人的时间) 而取最慢的两个过桥的前提是：已经过桥的人中,存在一个人,速度比未过桥的人快 (其实这个人永远就是no.2 因为no.2永远和no.1一起过桥而no.1永远是优先回来) 这样所浪费的时间是最少也就是最优的过桥方案

源码:

View Code

  1   internal class Women
  2     {
  3         /// <summary>
  4         /// 左边未过桥人集合
  5         /// </summary>
  6         private List<int> leftListWomen = new List<int>();
  7         /// <summary>
  8         /// 右边已过桥人集合
  9         /// </summary>
 10         private List<int> rightListWomen = new List<int>();
 11         /// <summary>
 12         /// 已过人数
 13         /// </summary>
 14         private int alreadyNum = 0;
 15         /// <summary>
 16         /// 应过人数
 17         /// </summary>
 18         private int shouldNum = 0;
 19         /// <summary>
 20         /// 共用时
 21         /// </summary>
 22         private int sumTime = 0;
 23 
 24         public Women(params int[] speed)
 25         {
 26             foreach (var item in speed)
 27             {
 28                 leftListWomen.Add(item);
 29                 shouldNum++;
 30             }
 31         }
 32         /// <summary>
 33         /// 是否已完成过桥
 34         /// </summary>
 35         private bool IsComplete
 36         {
 37             get
 38             {
 39                 return alreadyNum == shouldNum;
 40             }
 41         }
 42         /// <summary>
 43         /// 开始过桥
 44         /// </summary>
 45         /// <returns></returns>
 46         public string StartGapBridge()
 47         {
 48             string msg = string.Empty;
 49             while (!IsComplete)
 50             {
 51                 if (leftListWomen.Count >= 2)
 52                 {
 53                     //送大的过桥
 54                     if (IsRightWomenLessLeft())
 55                     {
 56                         leftListWomen.Sort();
 57                         msg += "过桥:" + leftListWomen[leftListWomen.Count - 1] + "和" + leftListWomen[leftListWomen.Count - 2] + Environment.NewLine;
 58                         sumTime += leftListWomen[leftListWomen.Count - 1];
 59                         rightListWomen.Add(leftListWomen[leftListWomen.Count - 1]);
 60                         rightListWomen.Add(leftListWomen[leftListWomen.Count - 2]);
 61                         leftListWomen.RemoveAt(leftListWomen.Count - 1);
 62                         leftListWomen.RemoveAt(leftListWomen.Count - 1);
 63                         alreadyNum = alreadyNum + 2;
 64                         if (!IsComplete)
 65                         {
 66                             //返回
 67                             rightListWomen.Sort();
 68                             msg += "返回:" + rightListWomen[0] + Environment.NewLine;
 69                             sumTime += rightListWomen[0];
 70                             leftListWomen.Add(rightListWomen[0]);
 71                             rightListWomen.RemoveAt(0);
 72                             alreadyNum--;
 73                         }
 74                     }
 75                     else
 76                     {
 77                         leftListWomen.Sort();
 78                         msg += "过桥:" + leftListWomen[0] + "和" + leftListWomen[1] + Environment.NewLine;
 79                         sumTime += leftListWomen[1];
 80                         rightListWomen.Add(leftListWomen[0]);
 81                         rightListWomen.Add(leftListWomen[1]);
 82                         leftListWomen.RemoveAt(0);
 83                         leftListWomen.RemoveAt(0);
 84                         alreadyNum = alreadyNum + 2;
 85                         if (!IsComplete)
 86                         {
 87                             //返回
 88                             rightListWomen.Sort();
 89                             msg += "返回:" + rightListWomen[0] + Environment.NewLine;
 90                             sumTime += rightListWomen[0];
 91                             leftListWomen.Add(rightListWomen[0]);
 92                             rightListWomen.RemoveAt(0);
 93                             alreadyNum--;
 94                         }
 95                     }
 96                 }
 97             }
 98             return msg + "共用时:" + sumTime;
 99         }
100 
101         /// <summary>
102         /// 是否右边女人的速度有比左边快的
103         /// </summary>
104         /// <returns></returns>
105         private bool IsRightWomenLessLeft()
106         {
107             foreach (int rightSpeed in rightListWomen)
108             {
109                 foreach (int leftSpeed in leftListWomen)
110                 {
111                     if (leftSpeed > rightSpeed)
112                     {
113                         return true;
114                     }
115                 }
116             }
117             return false;
118         }
119 
120     }

View Code

1   static void Main(string[] args)
2         {
3 
4             Women w1 = new Women(1, 2, 5, 10);
5             Console.WriteLine(w1.StartGapBridge());
6             Console.Read();
7         }

ps：我本来想上传打包源码发现找不到上传按钮...

如果这篇文章能够给与您帮助不妨点个推荐吧!