查找加起來給定數字的數字的子集

Question

我有一個問題，我需要使用C＃來解決。有一個十進制數字的數組（表示倉庫在不同時間收到的物料的數量）。該數組已按照接收數量的順序排序。我需要能夠找到總計達到指定總量的最早數量組合。例如，假設我有一些按時間順序排列的數量如下[13,6,9,8,23,18,4]，並說我的總量匹配是23.那麼我應該能夠得到[13,6,4]作爲匹配的子集，儘管[6,9,8]和[23]也是匹配的，但不是最早的。

什麼是最好的方法/算法呢？

我到目前爲止想出了一個相當天真的方法使用遞歸。

public class MatchSubset 
{ 
    private decimal[] qty = null; 
    private decimal matchSum = 0; 
    public int operations = 0; 
    public int[] matchedIndices = null; 
    public int matchCount = 0; 
    private bool SumUp(int i, int n, decimal sum) 
    { 
     operations++; 
     matchedIndices[matchCount++] = i; 
     sum += qty[i]; 
     if (sum == matchSum) 
      return true; 
     if (i >= n - 1) 
     { 
      matchCount--; 
      return false; 
     } 
     if (SumUp(i + 1, n, sum)) 
      return true; 

     sum -= qty[i]; 
     matchCount--; 
     return SumUp(i + 1, n, sum); 
    } 
    public bool Match(decimal[] qty, decimal matchSum) 
    { 
     this.qty = qty; 
     this.matchSum = matchSum; 
     matchCount = 0; 
     matchedIndices = new int[qty.Count()]; 
     return SumUp(0, qty.Count(), 0); 
    } 
} 

static void Main(string[] args) 
{ 
    var match = new MatchSubset(); 
    int maxQtys = 20; 
    Random rand = new Random(DateTime.Now.Millisecond); 
    decimal[] qty = new decimal[maxQtys]; 
    for (int i = 0; i < maxQtys - 2; i++) 
     qty[i] = rand.Next(1, 500); 

    qty[maxQtys - 2] = 99910; 
    qty[maxQtys - 1] = 77910; 
    DateTime t1 = DateTime.Now; 
    if (match.Match(qty, 177820)) 
    { 
     Console.WriteLine(DateTime.Now.Subtract(t1).TotalMilliseconds); 
     Console.WriteLine("Operations: " + match.operations); 
     for (int i = 0; i < match.matchCount; i++) 
     { 
      Console.WriteLine(match.matchedIndices[i]); 
     } 
    } 
} 

匹配子集可以短至一個元件，並且只要原始集（包含所有元件）。但爲了測試最糟糕的情況，在我的測試程序中，我使用了一個任意長的集合，其中只有最後兩個匹配給定的數字。

我看到在集合中有20個數字，它會調用遞歸函數超過一百萬次，最大遞歸深度爲20位。如果我在生產中碰到一組30個或更多數字，我擔心它會消耗很長時間。

有沒有辦法進一步優化呢？另外，看着降價，這是否是這樣的問題的錯誤地點？

Answer 1

我不能以革命性的東西結束，所以提出的解決方案只是一個不同的實施相同的蠻力算法，2優化。第一個優化是使用迭代實現而不是遞歸。我不認爲這很重要，因爲你更有可能最終失去時間而不是超出堆棧空間，但它仍然是一個很好的實現，並且不難實現。最重要的是第二個。這個想法是，在「前進」步驟中，任何時候當前總和大於目標總和時，能夠跳過檢查與當前項目具有更大或相等值的下一個項目。通常這是通過首先對輸入集合進行排序來完成的，這在您的情況下不適用。然而，在思考如何克服這個限制的同時，我意識到我所需要的就是讓每個項目的第一個下一個項目的索引值小於項目值，所以我可以跳到該索引直到我點擊結束。現在，雖然在最壞的情況下，兩種實現都以相同的方式執行，即可能不會在合理的時間內結束，但在許多實際情況下，優化的變體能夠非常快速地產生結果，而原始仍然不結束合理的時間。您可以通過玩maxQtys和maxQty參數來檢查差異。

這裏是實現進行了描述，帶有測試代碼：

using System; 
using System.Diagnostics; 
using System.Linq; 

namespace Tests 
{ 
    class Program 
    { 
     private static void Match(decimal[] inputQty, decimal matchSum, out int[] matchedIndices, out int matchCount, out int operations) 
     { 
      matchedIndices = new int[inputQty.Length]; 
      matchCount = 0; 
      operations = 0; 

      var nextLessQtyPos = new int[inputQty.Length]; 
      for (int i = inputQty.Length - 1; i >= 0; i--) 
      { 
       var currentQty = inputQty[i]; 
       int nextPos = i + 1; 
       while (nextPos < inputQty.Length) 
       { 
        var nextQty = inputQty[nextPos]; 
        int compare = nextQty.CompareTo(currentQty); 
        if (compare < 0) break; 
        nextPos = nextLessQtyPos[nextPos]; 
        if (compare == 0) break; 
       } 
       nextLessQtyPos[i] = nextPos; 
      } 

      decimal currentSum = 0; 
      for (int nextPos = 0; ;) 
      { 
       if (nextPos < inputQty.Length) 
       { 
        // Forward 
        operations++; 
        var nextSum = currentSum + inputQty[nextPos]; 
        int compare = nextSum.CompareTo(matchSum); 
        if (compare < 0) 
        { 
         matchedIndices[matchCount++] = nextPos; 
         currentSum = nextSum; 
         nextPos++; 
        } 
        else if (compare > 0) 
        { 
         nextPos = nextLessQtyPos[nextPos]; 
        } 
        else 
        { 
         // Found 
         matchedIndices[matchCount++] = nextPos; 
         break; 
        } 
       } 
       else 
       { 
        // Backward 
        if (matchCount == 0) break; 
        var lastPos = matchedIndices[--matchCount]; 
        currentSum -= inputQty[lastPos]; 
        nextPos = lastPos + 1; 
       } 
      } 
     } 

     public class MatchSubset 
     { 
      private decimal[] qty = null; 
      private decimal matchSum = 0; 
      public int operations = 0; 
      public int[] matchedIndices = null; 
      public int matchCount = 0; 
      private bool SumUp(int i, int n, decimal sum) 
      { 
       operations++; 
       matchedIndices[matchCount++] = i; 
       sum += qty[i]; 
       if (sum == matchSum) 
        return true; 
       if (i >= n - 1) 
       { 
        matchCount--; 
        return false; 
       } 
       if (SumUp(i + 1, n, sum)) 
        return true; 

       sum -= qty[i]; 
       matchCount--; 
       return SumUp(i + 1, n, sum); 
      } 
      public bool Match(decimal[] qty, decimal matchSum) 
      { 
       this.qty = qty; 
       this.matchSum = matchSum; 
       matchCount = 0; 
       matchedIndices = new int[qty.Count()]; 
       return SumUp(0, qty.Count(), 0); 
      } 
     } 

     static void Main(string[] args) 
     { 
      int maxQtys = 3000; 
      decimal matchQty = 177820; 
      var qty = new decimal[maxQtys]; 
      int maxQty = (int)(0.5m * matchQty); 
      var random = new Random(); 
      for (int i = 0; i < maxQtys - 2; i++) 
       qty[i] = random.Next(1, maxQty); 

      qty[maxQtys - 2] = 99910; 
      qty[maxQtys - 1] = 77910; 

      Console.WriteLine("Source: {" + string.Join(", ", qty.Select(v => v.ToString())) + "}"); 
      Console.WriteLine("Target: {" + matchQty + "}"); 

      int[] matchedIndices; 
      int matchCount; 
      int operations; 
      var sw = new Stopwatch(); 

      Console.Write("#1 processing..."); 
      sw.Restart(); 
      Match(qty, matchQty, out matchedIndices, out matchCount, out operations); 
      sw.Stop(); 
      ShowResult(matchedIndices, matchCount, operations, sw.Elapsed); 

      Console.Write("#2 processing..."); 
      var match = new MatchSubset(); 
      sw.Restart(); 
      match.Match(qty, matchQty); 
      sw.Stop(); 
      ShowResult(match.matchedIndices, match.matchCount, match.operations, sw.Elapsed); 

      Console.Write("Done."); 
      Console.ReadLine(); 
     } 

     static void ShowResult(int[] matchedIndices, int matchCount, int operations, TimeSpan time) 
     { 
      Console.WriteLine(); 
      Console.WriteLine("Time: " + time); 
      Console.WriteLine("Operations: " + operations); 
      if (matchCount == 0) 
       Console.WriteLine("No Match."); 
      else 
       Console.WriteLine("Match: {" + string.Join(", ", Enumerable.Range(0, matchCount).Select(i => matchedIndices[i].ToString())) + "}"); 
     } 
    } 
}