子集和问题

Question

我遇到了一个计数问题，这是 这个 问题的延续。我不是一个数学专业的人，所以很难理解建议解决方案中提到的“子集和问题”。

我有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个ArrayList中：

- alNewHowMuch（对应于alNumber） - alNewPrice（对应于alPrice） - alNewInID（对应于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和数字向数组中添加和删除内容。例如，当进行转入或购买时，我会像156、340这样将数字添加到ArrayList中，然后在进行转出或销售时再将它们删除，如156、340等。我的解决方案可以正常运行，但是问题是对于一些旧数据，员工输入的总数是1500而不是500+400+100+500。我该怎么做才能使其在Sell/TransferOut或Buy/Transfer In时，在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);
                            }
                        }
                    }

但它只在满足特定条件时才有效，对于其他情况则失败。

编辑：由于我的波兰变量名称让一些人感到惊讶（和被盲目刺眼），我将它们全部翻译成英文，以便简化和提高可见性。希望这能帮助我得到一些帮助 :-)

- MadBoy

---

你选择的标识符令人难以置信... - Joren

使用 switch 不当，两个 if 语句就足够了。 - Srinivas Reddy Thatiparthy

@Joren：用波兰语可能更有意义。 - Mark Byers

@Srinivas -> 我已经删去了这个开关的其他部分，以使它更容易。在此开关中有6个情况，其中3个我已经删去以简化问题。 - MadBoy

@Joren, Mark -> 是的，用波兰语更有意义，我还将一些变量翻译成了英语（像“购买”这样更难的变量，例如“Papiery wartościowe - Kupno”），以简化事情。我一个人编写代码，而且它是针对波兰文化的，因此保留英文标识符没有意义。 - MadBoy

Answer 1

这是我的算法。它的运行时间为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;
}

这个最后一个算法在约5毫秒内解决了100000个问题（但这是算法的最佳情况，在实际数据中会更慢）。

对于您的用途，这个算法可能已经足够快了（我没有看到任何明显的改进）。如果您输入了10000个产品，价格在0到20之间随机，并且您的目标是将它们加起来达到500，那么在我的笔记本电脑上可以在0.04秒内解决。

编辑：我刚刚在维基百科上读到，最好的已知算法是O(2^(n/2)*n)。而这个算法是O(2^(n/2))。我能得到图灵奖吗？

- Jules

---

为什么你说它是O(2^(n/2))？你在每次调用Insert时都遍历整个nums列表。我认为做这样的测试没有意义，因为很容易找到一个使得每种算法（伪多项式或指数级）都会失败的案例。你找到了一个伪多项式算法失败的案例（需要很长时间才能完成）：100000。这里有一个你的算法也需要很长时间才能完成的案例：10000个数字：1 2 3 4 ... 10000。搜索345600。另外，你只打印true或false，我认为打印数字也会增加一些开销。无论如何，这似乎比DP更快，所以+1，但是... - IVlad

然而，如果我们要处理如此高的数字，让我在从大学回来后实现我的随机算法：）。我认为这样更好，特别是当我们处理非常大的数字时。 - IVlad

哦，之前的算法实际上在你提到的测试案例中更快。那很奇怪... - Jules

你能测试比“one's”更高的值吗？比如千或十万？ - Krip

可以的。如果你使用一个有1000个元素的数组，也不会有任何影响。但是如果你使用一个包含许多不同值的大型数组，那么它会变得很慢。 - Jules

Answer 2

这取决于几个重要因素：你会有多少数字，它们的大小如何？此外，据我所知，你的数据可能会发生变化（添加/删除数字等），对吗？你需要多频繁地进行这些查询？

我将提供两种解决方案。我建议你使用第二种，因为我认为它更适合你的需求，并且更容易理解。 解决方案1-动态规划 让S [i] = true，如果我们可以使总和为i，则为false。

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] =用于生成总和i的最后一个数字。您应该相应地在上面的if条件中进行更新。

这个算法的时间复杂度为O(numberOfNumbers * maxSumOfAllNumbers)，这非常糟糕，特别是当您的数据发生更改时，必须重新运行此算法。即使只运行一次，也很慢，因为您的数字可能非常大，并且您可能有很多数字。事实上，“很多”是具有误导性的。如果您有100个数字，每个数字可以达到10,000，那么每次数据更改时，您将执行大约100 * 10,000 = 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;
            }
        }
    }

你需要进行一些错误检查，或许可以在类中存储上一个和，以便不允许使用与调用 Find 时不同的和来调用 GetLastResult。总之，这就是想法。

解决方案2 - 随机算法

现在，这更容易了。保持两个列表：usedNums 和 unusedNums。同时保留一个变量 usedSum，在任何时间点，它都包含 usedNums 列表中所有数字的总和。

每当你需要将一个数字插入到集合中时，也将其添加到其中一个列表中（无所谓哪个，但要随机选择，以便分布相对均匀）。相应地更新 usedSum。

每当你需要从集合中删除一个数字时，请找出它在哪个列表中。如果没有很多（这次很多意味着超过10,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的数字。

我认为这个算法应该适合你的需要。它非常适合处理数据集的变化，并且在处理大量数字时效果很好。此外，它不依赖于数字的大小，如果你有很大的数字，这非常有用。

如果您有任何问题，请发帖。

- IVlad

---

这个问题没有多项式时间的解法，动态规划的解法是伪多项式，所以它确实取决于数字的值。当然，这两种方法的速度相同，它们的输入都非常小且相似。此外，您的算法与我的略有不同。您只尝试为请求的总和给出答案，而我则尝试建立一个表格，其中包含所有总和的答案。当然，对于该问题实例，您的方法更好，但其复杂度相同。考虑调用 sub([1, 1, 1, 1, ...], <num ones>)。这应该会在许多“1”的情况下使其非常缓慢。 - IVlad

它应该能够执行大约一百万次操作，而只需要执行1000次。此外，我无法运行您的Python代码以进行测试。在@memoize行处出现错误，这是否应该被删除或手动实现？我不是一个Python专家。 - IVlad

@memoize注释将动态编程添加到朴素递归版本中。如果您删除它，程序将非常非常慢。我的程序在[1,1,1,1]和[1000,1000,1000,1000]上运行的速度完全相同，但是自底向上构建表格的动态编程算法在后者上需要更长时间。 - Jules

我的需求是将2到20个数字相加。希望这样能行 :-) 谢谢大家，非常感谢！我会回报进展情况。 - MadBoy

好的，我稍微改了一下实现。我放弃了递归解决方案，因为即使使用元组它也很慢，并且它使得获取所需索引更加困难。现在它是迭代的，即使对于1000个数字也可以立即完成，不容易出现堆栈溢出错误，并且允许您轻松获得更多的答案而不仅仅是一个true/false答案。它应该可以在.NET 3.5中编译并且没有问题。 - IVlad