用贪心算法来解决沙袋装箱问题

浏览数：32 / 时间：2015年06月08日

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

问题描述如下：
有一堆沙袋，每个沙袋中都转有从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 else
67 {
68 nowPos++;
69 }
70 }
71 
72 return sandLst2Tank;
73 }
74 }