子集和问题
我有一个计数问题，这是这个问题的延续。 我不是一个真正的数学家，所以我很难找出这个被称为分辨率的subset sum problem 。
我有4个ArrayList ，其中包含数据：alId，alTransaction，alNumber，alPrice
输入| 交易| 号码| 价钱
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（对alID的corrseponds）
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 = 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和数字添加和删除Array中的东西。 我正在向ArrayList添加数字，如156,340（当它是TransferIn或Buy时）等，然后我删除它们就像156,340那样（当它是TransferOut，卖出时）。 我的解决方案适用于此而没有问题。 我遇到的问题是，对于一些旧数据，员工输入的金额是1500而不是500 + 400 + 100 + 500。 我如何更改它，以便当有Sell/TransferOut或Buy/Transfer In并且在ArrayList中没有匹配时，它应该尝试从该ArrayList添加多个项目并找到组合成聚合的元素。
在我的代码里面，我尝试通过简单的总结来解决这个问题，当没有匹配时（index == 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 = 0; j --) { int tempIndex = (int) alTemp[j]; alNewHowMuch.RemoveAt(tempIndex); alNewPrice.RemoveAt(tempIndex); alNewInID.RemoveAt(tempIndex); } } }
但它只有在满足某些条件时才有效，而其余条件则无效。
编辑：由于你们中的一些人对我的波兰变量名称感到非常惊讶（并且是盲目的）我将所有这些变为英语，以简化和可见。 希望这会帮助我得到一些帮助:-)
你应该怎么做取决于一些重要的事情：你将拥有多少数字以及它们有多大？ 另外，据我所知，您的数据可以更改（添加/删除数字等），对吧？ 您需要多久进行一次这些查询？
我将提出两种解决方案。 我建议你使用第二种，因为我怀疑它对你需要的东西更好，而且更容易理解。
解决方案1 – 动态编程
S[i] = true if we can make sum i and false otherwise.让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个数字且每个数字可以大到10 000，那么每次数据更改时，您将执行大约100 * 10 000 = 1 000 000次操作。
知道这是一个很好的解决方案，但在实践中并没有真正有用，或者至少在你的情况下并非如此。
对于我建议的方法，他是一些C＃：
class Program { static void Main(string[] args) { List testList = new List (); 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 memo; private static Dictionary> prev; static SubsetSum() { memo = new Dictionary(); prev = new Dictionary>(); } public static bool Find(List inputArray, int sum) { memo.Clear(); prev.Clear(); memo[0] = true; prev[0] = new KeyValuePair(-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(i, num); } } } } return memo.ContainsKey(sum) && memo[sum]; } public static IEnumerable GetLastResult(int sum) { while (prev[sum].Key != -1) { yield return prev[sum].Key; sum -= prev[sum].Value; } } }
您可能应该进行一些错误检查，并且可能将最后一笔存储在类中，以便不允许使用与上次调用的Find之和不同的总和来调用GetLastResult 。 无论如何，这是个主意。
解决方案2 – 随机算法
现在，这更容易。 保留两个列表： usedNums和unusedNums 。 还要保留一个变量usedSum ，它在任何时间点都包含usedNums列表中所有数字的usedNums 。
每当你需要在你的集合中插入一个数字时，也要将它添加到两个列表中的一个（无关紧要，但是随机进行，以便有相对均匀的分布）。 相应地更新usedSum 。
每当你需要从你的集合中删除一个数字时，找出它所在的两个列表中的哪一个。只要你没有很多东西，你就可以用线性搜索来做这个（这次很多意味着超过10 000，也许在快速计算机上甚至是10万，并且假设你不经常连续地进行这种操作。无论如何，如果你需要它，可以优化线性搜索。）。 找到号码后，将其从列表中删除。 相应地更新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的数字。
我想这个算法应该对你需要的东西有好处。 它可以很好地处理数据集的更改，并且可以很好地处理大量数据。 它也不取决于数字有多大，如果您有大数字，这非常有用。
如果您有任何疑问，请发布。
这是我的算法。 它在O(2^(n/2))并在20毫秒内求解SubsetSum(1000, list-of-1000-ones) 。 查看IVladpost末尾的评论。
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(); 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 nums, int targetL) { var left = new List { 0 }; var right = new List { 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 Insert(int num, List nums) { var result = new List (); 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 nums, int target) { var remainingSum = nums.Sum(); var left = new List { 0 }; var right = new List { 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 Insert(int num, List nums, int min, int max) { var result = new List (); 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; }
最后一个在大约5毫秒内解决了100000个问题（但这是算法的最佳情况，现实世界数据会慢一些）。
为了您的使用，这个算法可能足够快（我没有看到任何明显的改进）。 如果您输入10,000个产品，其随机价格在0到20之间，并且您的目标是总和为500，那么在我的笔记本电脑上可以在0.04秒内解决。
编辑：我刚刚在维基百科上读到，最着名的算法是O(2^(n/2)*n) 。 这个是O(2^(n/2)) 。 我获得图灵奖吗？