子集總和問題

Question

我遇到了計數問題，這是this問題的延續。我不是一個真正的數學家，所以我很難找出這個建議作爲解決方案的subset sum problem。

我有4 ArrayList我在其中保存數據：alId，alTransaction，alNumber，alPrice

類型|交易| Number |價格
8 |購買| 95.00000000 | 305.00000000
8 |購買| 126.00000000 | 305.00000000
8 |購買| 93.00000000 | 306.00000000
8 |轉出| 221.00000000 | 305.00000000
8 |轉入| 221.00000000 | 305.00000000
8 |賣| | 93.00000000 | 360.00000000
8 |賣| | 95.00000000 | 360.00000000
8 |賣| | 126.00000000 | 360.00000000
8 |購買| 276.00000000 | 380.00000000

最終我試圖得到什麼的留給客戶，什麼是離開我投入3名數組列表：
- alNewHowMuch（相當於alNumber），
- alNewPrice（相當於alPrice）
- alNewInID（corrseponds到alID）

 ArrayList alNewHowMuch = new ArrayList(); 
     ArrayList alNewPrice = new ArrayList(); 
     ArrayList alNewInID = new ArrayList(); 
     for (int i = 0; i < alTransaction.Count; i++) { 
      string transaction = (string) alTransaction[i]; 
      string id = (string) alID[i]; 
      decimal price = (decimal) alPrice[i]; 
      decimal number = (decimal) alNumber[i]; 
      switch (transaction) { 
       case "Transfer out": 
       case "Sell": 
        int index = alNewHowMuch.IndexOf(number); 
        if (index != -1) { 
         alNewHowMuch.RemoveAt(index); 
         alNewPrice.RemoveAt(index); 
         alNewInID.RemoveAt(index); 
        } else { 
         ArrayList alTemp = new ArrayList(); 
         decimal sum = 0; 
         for (int j = 0; j < alNewHowMuch.Count; j ++) { 
          string tempid = (string) alNewInID[j]; 
          decimal tempPrice = (decimal) alNewPrice[j]; 
          decimal tempNumbers = (decimal) alNewHowMuch[j]; 
          if (id == tempid && tempPrice == price) { 
           alTemp.Add(j); 
           sum = sum + tempNumbers; 
          } 
         } 
         if (sum == number) { 
          for (int j = alTemp.Count - 1; j >= 0; j --) { 
           int tempIndex = (int) alTemp[j]; 
           alNewHowMuch.RemoveAt(tempIndex); 
           alNewPrice.RemoveAt(tempIndex); 
           alNewInID.RemoveAt(tempIndex); 
          } 
         } 
        } 
        break; 
       case "Transfer In": 
       case "Buy": 
        alNewHowMuch.Add(number); 
        alNewPrice.Add(price); 
        alNewInID.Add(id); 
        break; 
      } 
     } 

基本上我添加和從陣列根據交易類型，交易ID和號碼去除的東西。我將數字添加到ArrayList 156,340（當它是TransferIn或Buy）等等，然後刪除它們，比如156,340（當它是TransferOut，Sell）。我的解決方案可以毫無問題地工作。我遇到的問題是，對於一些舊數據，員工正在輸入1500而不是500 + 400 + 100 + 500。我將如何更改它，以便在存在Sell/TransferOut或Buy/Transfer In且ArrayList內沒有匹配時，它應該嘗試添加來自該ArrayList的多個項目並查找組合爲聚合的元素。

裏面我的代碼，我想，當沒有比賽（指數== 1）

    int index = alNewHowMuch.IndexOf(number); 
        if (index != -1) { 
         alNewHowMuch.RemoveAt(index); 
         alNewPrice.RemoveAt(index); 
         alNewInID.RemoveAt(index); 
        } else { 
         ArrayList alTemp = new ArrayList(); 
         decimal sum = 0; 
         for (int j = 0; j < alNewHowMuch.Count; j ++) { 
          string tempid = (string) alNewInID[j]; 
          decimal tempPrice = (decimal) alNewPrice[j]; 
          decimal tempNumbers = (decimal) alNewHowMuch[j]; 
          if (id == tempid && tempPrice == price) { 
           alTemp.Add(j); 
           sum = sum + tempNumbers; 
          } 
         } 
         if (sum == number) { 
          for (int j = alTemp.Count - 1; j >= 0; j --) { 
           int tempIndex = (int) alTemp[j]; 
           alNewHowMuch.RemoveAt(tempIndex); 
           alNewPrice.RemoveAt(tempIndex); 
           alNewInID.RemoveAt(tempIndex); 
          } 
         } 
        } 

但它只能在滿足一定的條件，以及失敗的休息，以解決簡單的總結一切問題。

編輯：由於你們中的一些人對我的波蘭變量名稱感到驚訝（並且不知所措），所以我把它們全部翻譯成英文以簡化和可見性。希望這會幫助我得到一些幫助:-)

Answer 1

你應該怎麼做這取決於一些重要的事情：你會有多少號碼，他們會有多大？另外，據我所知，你的數據可以改變（添加/刪除數字等），對吧？您需要多長時間才能完成這些查詢？

我會提出了兩種解決方案。我建議你使用第二種方法，因爲我認爲它更適合你的需求，而且它更容易理解。

解決方案1 ​​ - 動態規劃

讓S[i] = true if we can make sum i and false otherwise.

S[0] = true // we can always make sum 0: just don't choose any number 
S[i] = false for all i != 0 
for each number i in your input 
    for s = MaxSum downto i 
     if (S[s - i] == true) 
      S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i. 

獲得實際的數字，讓你和你應該保持的另一種載體P[i] = the last number that was used to make sum i。您將在上面的if條件中相應地更新此項。

這個的時間複雜度爲O(numberOfNumbers * maxSumOfAllNumbers)，這很糟糕，特別是因爲每當數據發生變化時都必須重新運行此算法。只要你的數字很大，而且你可以有很多這樣的數字，即使是一次運行也很慢。事實上，「很多」是誤導性的。如果您有100個號碼，每個號碼可以大到10000，那麼每次數據更改時，您將執行大約100 * 10000 = 1 000 000次操作。

這是一個很好的解決方案，但在實踐中並不真正有用，或者至少在您的情況下我不這麼認爲。

他一些C＃的方法，我建議：

class Program 
     { 
     static void Main(string[] args) 
     { 
      List<int> testList = new List<int>(); 

      for (int i = 0; i < 1000; ++i) 
      { 
       testList.Add(1); 
      } 

      Console.WriteLine(SubsetSum.Find(testList, 1000)); 

      foreach (int index in SubsetSum.GetLastResult(1000)) 
      { 
       Console.WriteLine(index); 
      } 
     } 
    } 

    static class SubsetSum 
    { 
     private static Dictionary<int, bool> memo; 
     private static Dictionary<int, KeyValuePair<int, int>> prev; 

     static SubsetSum() 
     { 
      memo = new Dictionary<int, bool>(); 
      prev = new Dictionary<int, KeyValuePair<int, int>>(); 
     } 

     public static bool Find(List<int> inputArray, int sum) 
     { 
      memo.Clear(); 
      prev.Clear(); 

      memo[0] = true; 
      prev[0] = new KeyValuePair<int,int>(-1, 0); 

      for (int i = 0; i < inputArray.Count; ++i) 
      { 
       int num = inputArray[i]; 
       for (int s = sum; s >= num; --s) 
       { 
        if (memo.ContainsKey(s - num) && memo[s - num] == true) 
        { 
         memo[s] = true; 

         if (!prev.ContainsKey(s)) 
         { 
          prev[s] = new KeyValuePair<int,int>(i, num); 
         } 
        } 
       } 
      } 

      return memo.ContainsKey(sum) && memo[sum]; 
     } 

     public static IEnumerable<int> GetLastResult(int sum) 
     { 
      while (prev[sum].Key != -1) 
      { 
       yield return prev[sum].Key; 
       sum -= prev[sum].Value; 
      } 
     } 
    } 

你應該做一些錯誤檢查也許，也許最後一筆存放在班上以免讓調用GetLastResult有不同的可能性總和比Find總和最後被調用。無論如何，這是主意。

解決方案2 - 隨機算法

現在，這是更容易。保留兩個列表：usedNums和unusedNums。同時保留一個變量usedSum，該值在任何時間點都包含usedNums列表中所有數字的總和。

無論何時您需要在您的設置中插入一個數字，還將其添加到兩個列表中的一個（無關緊要，但是隨機執行，因此分佈相對均勻）。相應地更新usedSum。

每當你需要從你的設置中刪除一個數字，找出它所在的兩個列表中的哪一個。只要你沒有很多（這次很多意味着結束10 000，在一臺快速計算機上可能甚至達到100 000，並且假設你不經常和連續地執行此操作。無論如何，如果需要，可以優化線性搜索）。找到號碼後，將其從列表中刪除。相應地更新usedSum。

每當你需要找出是否有您所設定的數字，總和爲數字S，使用此算法：

while S != usedSum 
    if S > usedSum // our current usedSum is too small 
     move a random number from unusedNums to usedNums and update usedSum 
    else // our current usedSum is too big 
     move a random number from usedNums to unusedNums and update usedSum 

在算法結束時，列表usedNums會給你他們的數字總和是S。

這個算法應該適合你需要的東西，我想。它能夠很好地處理數據集的變化，並且適用於高數量的數據。它也不取決於數字的大小，如果你有大數字，這非常有用。

如果您有任何問題，請發佈。

Answer 2

這是我的算法。它運行在O(2^(n/2))並在20毫秒內解決了SubsetSum(1000, list-of-1000-ones)。看到在IVlad的帖子末尾的評論。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Diagnostics; 

namespace SubsetSum 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      var ns = new List<int>(); 
      for (int i = 0; i < 1000; i++) ns.Add(1); 
      var s1 = Stopwatch.StartNew(); 
      bool result = SubsetSum(ns, 1000); 
      s1.Stop(); 
      Console.WriteLine(result); 
      Console.WriteLine(s1.Elapsed); 
      Console.Read(); 
     } 

     static bool SubsetSum(ist<int> nums, int targetL) 
     { 
      var left = new List<int> { 0 }; 
      var right = new List<int> { 0 }; 
      foreach (var n in nums) 
      { 
       if (left.Count < right.Count) left = Insert(n, left); 
       else right = Insert(n, right); 
      } 
      int lefti = 0, righti = right.Count - 1; 
      while (lefti < left.Count && righti >= 0) 
      { 
       int s = left[lefti] + right[righti]; 
       if (s < target) lefti++; 
       else if (s > target) righti--; 
       else return true; 
      } 
      return false; 
     } 

     static List<int> Insert(int num, List<int> nums) 
     { 
      var result = new List<int>(); 
      int lefti = 0, left = nums[0]+num; 
      for (var righti = 0; righti < nums.Count; righti++) 
      { 

       int right = nums[righti]; 
       while (left < right) 
       { 
        result.Add(left); 
        left = nums[++lefti] + num; 
       } 
       if (right != left) result.Add(right); 
      } 
      while (lefti < nums.Count) result.Add(nums[lefti++] + num); 
      return result; 
     } 
    } 
} 

這裏是一個改進版本，修剪集：

static bool SubsetSum(List<int> nums, int target) 
{ 
    var remainingSum = nums.Sum(); 
    var left = new List<int> { 0 }; 
    var right = new List<int> { 0 }; 
    foreach (var n in nums) 
    { 
     if (left.Count == 0 || right.Count == 0) return false; 
     remainingSum -= n; 
     if (left.Count < right.Count) left = Insert(n, left, target - remainingSum - right.Last(), target); 
     else right = Insert(n, right, target - remainingSum - left.Last(), target); 
    } 
    int lefti = 0, righti = right.Count - 1; 
    while (lefti < left.Count && righti >= 0) 
    { 
     int s = left[lefti] + right[righti]; 
     if (s < target) lefti++; 
     else if (s > target) righti--; 
     else return true; 
    } 
    return false; 
} 

static List<int> Insert(int num, List<int> nums, int min, int max) 
{ 
    var result = new List<int>(); 
    int lefti = 0, left = nums[0]+num; 
    for (var righti = 0; righti < nums.Count; righti++) 
    { 

     int right = nums[righti]; 
     while (left < right) 
     { 
      if (min <= left && left <= max) result.Add(left); 
      left = nums[++lefti] + num; 
     } 
     if (right != left && min <= right && right <= max) result.Add(right); 
    } 
    while (lefti < nums.Count) 
    { 
     left = nums[lefti++] + num; 
     if (min <= left && left <= max) result.Add(left); 
    } 
    return result; 
} 

這最後一個100000成的人在大約5毫秒解決了這個問題（不過這是算法的最佳情況下，真實世界的數據會更慢）。

爲了您的使用，此算法可能足夠快（並且我沒有看到任何明顯的改進）。如果您在0到20之間輸入10,000個隨機價格的產品，並且您的目標是總計爲500，那麼我的筆記本電腦將在0.04秒內解決問題。

編輯：我剛剛在維基百科上讀到最知名的算法是O(2^(n/2)*n)。這一個是O(2^(n/2))。我有圖靈獎嗎？