子集总和问题

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))。我有图灵奖吗？