子集合加总问题

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=1000 000个操作。

这是一个很好的解决方案,但在实践中并不真正有用,或者至少在你的情况下不有用。

他是我建议的方法的专家:

   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 在任何时间点,它包含 使用数字 名单。

无论何时需要在集合中插入一个数字,也要将其添加到两个列表中的一个列表中(不重要,但要随机进行,这样分布相对均匀)。更新 使用金额 因此。

每当你需要从集合中删除一个数字时,找出它在两个列表中的哪一个。你可以用线性seach来做这个,只要你没有很多(这一次很多意味着超过10000,甚至100000在快速计算机上,假设你不经常和快速连续地做这个操作。不管怎样,如果需要的话,可以对线性搜索进行优化)。找到号码后,将其从列表中删除。更新 使用金额 因此。

每当你需要找出你的集合中是否有数字,这个和就是一个数。 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

在算法的末尾,列表 使用数字 会给你总数是多少的数字 S .

我认为这个算法应该适合你的需要。它可以很好地处理对数据集的更改,并在高数字计数下工作良好。它也不取决于数字有多大,如果你有大的数字,这是非常有用的。

如有任何问题,请发帖。

这是我的算法。它运行在 O(2^(n/2)) 解决 SubsetSum(1000, list-of-1000-ones) 在20毫秒内。见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)) . 我有图灵奖吗?