用貪心算法來解決沙袋裝箱問題

這是一個百度知道上的沙袋裝箱問題。我解決這個問題的基本思路是使用貪心算法，也叫做貪婪算法。貪心算法的原則是找出當前看來是最優的解決方案。

問題描述如下：有一堆沙袋，每個沙袋中都轉有從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 }