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

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

问题描述如下:
有一堆沙袋,每个沙袋中都转有从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 }
原文地址:https://www.cnblogs.com/liu-binq63/p/4343966.html