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

这是⼀个百度知道上的。我解决这个问题的基本思路是使⽤贪⼼算法，也叫做贪婪算法。贪⼼算法的原则是找出当前看来是最优的解决⽅案。

问题描述如下：

有⼀堆沙袋，每个沙袋中都转有从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 sandLst = new List();12 sandLst.AddRange(sandPackages);13

14 // 排序

15 sandLst.Sort();

16 // 翻转，翻转后，内部排序为从⼤到⼩17 sandLst.Reverse();18

19 List> tankLst = new List>();20

21 // 循环，处理数组，直到所有数据均被取出22 while (sandLst.Count != 0)23 {

24 // 找出⼀个数据相加最接近100的序列

25 tankLst.Add(Add2Tank(sandLst, tankSize));26 }27

28 // 显⽰

29 foreach (List 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 Add2Tank(List sandLst, int tankSize)50 {

51 List sandLst2Tank = new List();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]; sandLst.RemoveAt(nowPos);65 }66 else67 {

68 nowPos++;69 }70 }71

72 return sandLst2Tank;73 }74 }