你的位置:首页 > ASP.net教程

[ASP.net教程]用贪心算法来解决沙袋装箱问题


这是一个百度知道上的沙袋装箱问题。我解决这个问题的基本思路是使用贪心算法,也叫做贪婪算法。贪心算法的原则是找出当前看来是最优的解决方案。

 

问题描述如下:
有一堆沙袋,每个沙袋中都转有从1到100不等的沙子。
现在要求把这堆沙袋装入容积为100的箱子中。
问题是,如何用最少的箱子装这些沙袋?

我的思路是这样的:
如果想用最少的箱子,那么,箱子就要尽可能的装满。为了实现这个目标,就需要考虑组合的策略了。
数量比较大的沙袋,和其他沙袋组合起来比较困难,所以要优先放入箱子中,然后再和其他沙袋组合。
所以算法应该是这样的:
首先从大到小排序,得到序列A,
然后取出第一个元素(最大的元素),并把这个元素从序列A中删除。
然后取出第下一个元素,把这个元素和第一个元素相加,如果小于100,则把此元素从序列A中删除,然后继续取下一个元素做本步骤操作。
如果大于100,则跳过此元素,继续执行本步骤,直到所有元素遍历完成。
然后把上述序列记录下来,按照上述步骤计算序列A,直到序列A中没有元素为止。
代码如下:

 1 class Program 2 { 3 static void Main(string[] args) 4 { 5 try 6 { 7 int[] sandPackages = new int[] { 23, 42, 63, 66, 23, 42, 65, 23, 5, 32, 65, 20 }; 8  9 int tankSize = 100;10 11 List<int> sandLst = new List<int>();12 sandLst.AddRange(sandPackages);13 14 // 排序15 sandLst.Sort();16 // 翻转,翻转后,内部排序为从大到小17 sandLst.Reverse();18 19 List<List<int>> tankLst = new List<List<int>>();20 21 // 循环,处理数组,直到所有数据均被取出22 while (sandLst.Count != 0)23 {24 // 找出一个数据相加最接近100的序列25 tankLst.Add(Add2Tank(sandLst, tankSize));26 }27 28 // 显示29 foreach (List<int> sands in tankLst)30 {31 int temp = 0;32 foreach (int sand in sands)33 {34 temp += sand;35 Console.Write(sand);36 Console.Write(" ");37 }38 Console.Write("total:" + temp);39 Console.WriteLine();40 }41 42 }43 catch (Exception ex)44 {45 throw ex;46 }47 }48 49 private static List<int> Add2Tank(List<int> sandLst, int tankSize)50 {51 List<int> sandLst2Tank = new List<int>();52 int nowPos = 0; // 当前位置53 int nowSize = 0; // 当前合计54 // 遍历数组55 while (nowPos < sandLst.Count)56 {57 // 把当前位置的数值加到当前合计58 if ((nowSize + sandLst[nowPos]) <= 100)59 {60 // 如果计算后的当前合计小于等于100 ,则把当前位置的数据放入到待输出列表(即装箱)61 // 并从原始数组中移除62 sandLst2Tank.Add(sandLst[nowPos]);63 nowSize += sandLst[nowPos];64 sandLst.RemoveAt(nowPos);65 }66 else67 {68 nowPos++;69 }70 }71 72 return sandLst2Tank;73 }74 }