找到你要的答案

Q:Find all k-size subsets with sum s of an n-size bag of duplicate unsorted positive integers

Q:发现与重复无序的正整数n个大小的一个包和所有的k-子集

Please note that this is required for a C# .NET 2.0 project (Linq not allowed).

I know very similar questions have been asked here and I have already produce some working code (see below) but still would like an advice as to how to make the algorithm faster given k and s conditions.

This is what I've learnt so far: Dynamic programming is the most efficient way to finding ONE (not all) subsets. Please correct me if I am wrong. And is there a way of repeatedly calling the DP code to produce newer subsets till the bag (set with duplicates) is exhausted?

If not, then is there a way that may speed up the backtracking recursive algorithm I have below which does produce what I need but runs in O(2^n), I think, by taking s and k into account?

Here is my fixed bag of numbers that will NEVER change with n=114 and number range from 3 to 286:

    int[] numbers = new int[]
    {
        7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
        123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
        112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
        34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
        54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
        60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
        14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
        28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
        29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
        15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
        11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
        5, 4, 5, 6
    };

Requirements

  • Space limit to 2-3GB max but time should be O(n^something) not (something^n).

  • The bag must not be sorted and duplicate must not be removed.

  • The result should be the indices of the numbers in the matching subset, not the numbers themselves (as we have duplicates).

Dynamic Programming Attempt

Here is the C# dynamic programming version adapted from an answer to a similar question here on stackoverflow.com:

using System;
using System.Collections.Generic;

namespace Utilities
{
    public static class Combinations
    {
        private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>();
        private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>();
        static Combinations()
        {
            m_memo.Clear();
            m_previous.Clear();
            m_memo[0] = true;
            m_previous[0] = new KeyValuePair<int, int>(-1, 0);

        }

        public static bool FindSubset(IList<int> set, int sum)
        {
            //m_memo.Clear();
            //m_previous.Clear();
            //m_memo[0] = true;
            //m_previous[0] = new KeyValuePair<int, int>(-1, 0);

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

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

            return m_memo.ContainsKey(sum) && m_memo[sum];
        }
        public static IEnumerable<int> GetLastIndex(int sum)
        {
            while (m_previous[sum].Key != -1)
            {
                yield return m_previous[sum].Key;
                sum -= m_previous[sum].Value;
            }
        }

        public static void SubsetSumMain(string[] args)
        {
            int[] numbers = new int[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        };

            int sum = 400;
            //int size = 4; // don't know to use in dynamic programming

            // call dynamic programming
            if (Numbers.FindSubset(numbers, sum))
            {
                foreach (int index in Numbers.GetLastIndex(sum))
                {
                    Console.Write((index + 1) + "." + numbers[index] + "\t");
                }
                Console.WriteLine();
            }
            Console.WriteLine();

            Console.ReadKey();
        }
    }
}

Recursive Programming Attempt

and Here is the C# recursive programming version adapted from an answer to a similar question here on stackoverflow.com:

using System;
using System.Collections.Generic;

namespace Utilities
{
    public static class Combinations
    {
        private static int s_count = 0;
        public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
        {
            if ((numbers.Length <= index) || (current > sum)) return 0;
            if (result == null) result = new List<int>();

            List<int> temp = new List<int>(result);
            if (current + numbers[index] == sum)
            {
                temp.Add(index);
                if ((size == 0) || (temp.Count == size))
                {
                    s_count++;
                }
            }
            else if (current + numbers[index] < sum)
            {
                temp.Add(index);
                CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
            }

            CountSubsets(numbers, index + 1, current, sum, size, result);
            return s_count;
        }

        private static List<List<int>> m_subsets = new List<List<int>>();
        public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
        {
            if ((numbers.Length <= index) || (current > sum)) return m_subsets;
            if (result == null) result = new List<int>();

            List<int> temp = new List<int>(result);
            if (current + numbers[index] == sum)
            {
                temp.Add(index);
                if ((size == 0) || (temp.Count == size))
                {
                    m_subsets.Add(temp);
                }
            }
            else if (current + numbers[index] < sum)
            {
                temp.Add(index);
                FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
            }

            FindSubsets(numbers, index + 1, current, sum, size, result);

            return m_subsets;
        }

        public static void SubsetSumMain(string[] args)
        {
            int[] numbers = new int[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        };

            int sum = 17;
            int size = 2;

            // call backtracking recursive programming
            Console.WriteLine("CountSubsets");
            int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null);
            Console.WriteLine("Count = " + count);
            Console.WriteLine();

            // call backtracking recursive programming
            Console.WriteLine("FindSubsets");
            List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null);
            for (int i = 0; i < subsets.Count; i++)
            {
                if (subsets[i] != null)
                {
                    Console.Write((i + 1).ToString() + ":\t");
                    for (int j = 0; j < subsets[i].Count; j++)
                    {
                        int index = subsets[i][j];
                        Console.Write((index + 1) + "." + numbers[index] + " ");
                    }
                    Console.WriteLine();
                }
            }
            Console.WriteLine("Count = " + subsets.Count);

            Console.ReadKey();
        }
    }
}

Please let me know how to restrict the dynamic programming version to subsets of size k and if I can call it repeatedly so it returns different subsets on every call until there are no more matching subsets.

Also I am not sure where to initialize the memo of the DP algorithm. I did it in the static constructor which auto-runs when accessing any method. Is this the correct initialization place or does it need to be moved to inside the FindSunset() method [commented out]?

As for the recursive version, is it backtracking? and how can we speed it up. It works correctly and takes k and s into account but totally inefficient.

Let's make this thread the mother of all C# SubsetSum related questions!

请注意,这是一个C #需要.NET 2项目(LINQ不允许)。

我知道这里也有类似的问题,我已经提出了一些工作代码(见下文),但我还是想建议一下如何在k和S条件下使算法更快。

This is what I've learnt so far: Dynamic programming is the most efficient way to finding ONE (not all) subsets. Please correct me if I am wrong. And is there a way of repeatedly calling the DP code to produce newer subsets till the bag (set with duplicates) is exhausted?

如果没有,那么有没有一种方法,可以加快回溯递归算法我下面有什么,我需要,但运行在O(2 N N),我认为,采取S和K考虑?

这里是我的固定包的数字,永远不会改变与N = 114和数字范围从3到286:

    int[] numbers = new int[]
    {
        7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
        123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
        112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
        34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
        54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
        60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
        14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
        28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
        29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
        15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
        11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
        5, 4, 5, 6
    };

要求

  • Space limit to 2-3GB max but time should be O(n^something) not (something^n).

  • 不能将袋子分类和复制,不能移除。

  • The result should be the indices of the numbers in the matching subset, not the numbers themselves (as we have duplicates).

动态规划的尝试

这里是C #动态编程版本改编自回答类似的问题在stackoverflow.com:

using System;
using System.Collections.Generic;

namespace Utilities
{
    public static class Combinations
    {
        private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>();
        private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>();
        static Combinations()
        {
            m_memo.Clear();
            m_previous.Clear();
            m_memo[0] = true;
            m_previous[0] = new KeyValuePair<int, int>(-1, 0);

        }

        public static bool FindSubset(IList<int> set, int sum)
        {
            //m_memo.Clear();
            //m_previous.Clear();
            //m_memo[0] = true;
            //m_previous[0] = new KeyValuePair<int, int>(-1, 0);

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

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

            return m_memo.ContainsKey(sum) && m_memo[sum];
        }
        public static IEnumerable<int> GetLastIndex(int sum)
        {
            while (m_previous[sum].Key != -1)
            {
                yield return m_previous[sum].Key;
                sum -= m_previous[sum].Value;
            }
        }

        public static void SubsetSumMain(string[] args)
        {
            int[] numbers = new int[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        };

            int sum = 400;
            //int size = 4; // don't know to use in dynamic programming

            // call dynamic programming
            if (Numbers.FindSubset(numbers, sum))
            {
                foreach (int index in Numbers.GetLastIndex(sum))
                {
                    Console.Write((index + 1) + "." + numbers[index] + "\t");
                }
                Console.WriteLine();
            }
            Console.WriteLine();

            Console.ReadKey();
        }
    }
}

递归程序设计的尝试

这是C #递归编程版本改编自回答类似的问题在stackoverflow.com:

using System;
using System.Collections.Generic;

namespace Utilities
{
    public static class Combinations
    {
        private static int s_count = 0;
        public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
        {
            if ((numbers.Length <= index) || (current > sum)) return 0;
            if (result == null) result = new List<int>();

            List<int> temp = new List<int>(result);
            if (current + numbers[index] == sum)
            {
                temp.Add(index);
                if ((size == 0) || (temp.Count == size))
                {
                    s_count++;
                }
            }
            else if (current + numbers[index] < sum)
            {
                temp.Add(index);
                CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
            }

            CountSubsets(numbers, index + 1, current, sum, size, result);
            return s_count;
        }

        private static List<List<int>> m_subsets = new List<List<int>>();
        public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
        {
            if ((numbers.Length <= index) || (current > sum)) return m_subsets;
            if (result == null) result = new List<int>();

            List<int> temp = new List<int>(result);
            if (current + numbers[index] == sum)
            {
                temp.Add(index);
                if ((size == 0) || (temp.Count == size))
                {
                    m_subsets.Add(temp);
                }
            }
            else if (current + numbers[index] < sum)
            {
                temp.Add(index);
                FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
            }

            FindSubsets(numbers, index + 1, current, sum, size, result);

            return m_subsets;
        }

        public static void SubsetSumMain(string[] args)
        {
            int[] numbers = new int[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        };

            int sum = 17;
            int size = 2;

            // call backtracking recursive programming
            Console.WriteLine("CountSubsets");
            int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null);
            Console.WriteLine("Count = " + count);
            Console.WriteLine();

            // call backtracking recursive programming
            Console.WriteLine("FindSubsets");
            List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null);
            for (int i = 0; i < subsets.Count; i++)
            {
                if (subsets[i] != null)
                {
                    Console.Write((i + 1).ToString() + ":\t");
                    for (int j = 0; j < subsets[i].Count; j++)
                    {
                        int index = subsets[i][j];
                        Console.Write((index + 1) + "." + numbers[index] + " ");
                    }
                    Console.WriteLine();
                }
            }
            Console.WriteLine("Count = " + subsets.Count);

            Console.ReadKey();
        }
    }
}

请让我知道如何限制动态编程版本的大小k的子集,如果我可以调用它反复,所以它返回不同的子集在每个调用,直到有没有更多的匹配子集。

我也不知道哪里来初始化DP算法的备忘录。我是在静态构造函数中实现的,它在访问任何方法时自动运行。这是正确的初始化的地方还是需要搬到里面的findsunset()方法[评论]吗?

至于递归版本,它是回溯吗?我们怎样才能加快速度。它的工作原理正确,并考虑K和S考虑,但完全低效。

让我们把这个线程的所有C # subsetsum相关问题的妈妈!

answer1: 回答1:

My previous answer works on the principle of cutting off the number of combinations to check. But this can be improved significantly once you sort the array. The principle is similar, but since the solution is entirely different, I've decided to put it in a separate answer.

I was careful to use only .Net Framework 2.0 features. Might add a visual explanation later, but the comments should be enough.

class Puzzle
{
    private readonly int[] _tailSums;
    public readonly SubsetElement[] Elements;
    public readonly int N;

    public Puzzle(int[] numbers)
    {
        // Set N and make Elements array
        // (to remember the original index of each element)
        this.N = numbers.Length;
        this.Elements = new SubsetElement[this.N];

        for (var i = 0; i < this.N; i++)
        {
            this.Elements[i] = new SubsetElement(numbers[i], i);
        }

        // Sort Elements descendingly by their Number value
        Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number));

        // Save tail-sums to allow immediate access by index
        // Allow immedate calculation by index = N, to sum 0
        this._tailSums = new int[this.N + 1];
        var sum = 0;

        for (var i = this.N - 1; i >= 0; i--)
        {
            this._tailSums[i] = sum += this.Elements[i].Number;
        }
    }

    public void Solve(int s, Action<SubsetElement[]> callback)
    {
        for (var k = 1; k <= this.N; k++)
            this.Solve(k, s, callback);
    }

    public void Solve(int k, int s, Action<SubsetElement[]> callback)
    {
        this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback);
    }

    private void ScanSubsets(int startIndex, int k, int s,
                             List<SubsetElement> subset, Action<SubsetElement[]> cb)
    {
        // No more numbers to add, and current subset is guranteed to be valid
        if (k == 0)
        {
            // Callback with current subset
            cb(subset.ToArray());
            return;
        }

        // Sum the smallest k elements
        var minSubsetStartIndex = this.N - k;
        var minSum = this._tailSums[minSubssetStartIndex];

        // Smallest possible sum is greater than wanted sum,
        // so a valid subset cannot be found
        if (minSum > s)
        {
            return;
        }

        // Find largest number that satisfies the condition
        // that a valid subset can be found
        minSum -= this.Elements[minSubsetStartIndex].Number;

        // But remember the last index that satisfies the condition
        var minSubsetEndIndex = minSubsetStartIndex;

        while (minSubsetStartIndex > startIndex &&
               minSum + this.Elements[minSubsetStartIndex - 1].Number <= s)
        {
            minSubsetStartIndex--;
        }

        // Find the first number in the sorted sequence that is
        // the largest number we just found (in case of duplicates)
        while (minSubsetStartIndex > startIndex &&
               Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1])
        {
            minSubsetStartIndex--;
        }

        // [minSubsetStartIndex .. maxSubsetEndIndex] is the
        // full range we must check in recursion

        for (var subsetStartIndex = minSubsetStartIndex;
             subsetStartIndex <= minSubsetEndIndex;
             subsetStartIndex++)
        {
            // Find the largest possible sum, which is the sum of the
            // k first elements, starting at current subsetStartIndex
            var maxSum = this._tailSums[subsetStartIndex] -
                         this._tailSums[subsetStartIndex + k];

            // The largest possible sum is less than the wanted sum,
            // so a valid subset cannot be found
            if (maxSum < s)
            {
                return;
            }

            // Add current number to the subset
            var x = this.Elements[subsetStartIndex];
            subset.Add(x);

            // Recurse through the sub-problem to the right
            this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb);

            // Remove current number and continue loop
            subset.RemoveAt(subset.Count - 1);
        }
    }

    public sealed class SubsetElement
    {
        public readonly int Number;
        public readonly int Index;

        public SubsetElement(int number, int index)
        {
            this.Number = number;
            this.Index = index;
        }

        public override string ToString()
        {
            return string.Format("{0}({1})", this.Number, this.Index);
        }
    }
}

Usage and performance testing:

private static void Main()
{
    var sw = Stopwatch.StartNew();
    var puzzle = new Puzzle(new[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        });

    puzzle.Solve(2, 17, PuzzleOnSubsetFound);

    sw.Stop();
    Console.WriteLine("Subsets found: " + _subsetsCount);
    Console.WriteLine(sw.Elapsed);
}

private static int _subsetsCount;

private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset)
{
    _subsetsCount++;
    return; // Skip prints when speed-testing

    foreach (var el in subset)
    {
        Console.Write(el.ToString());
        Console.Write("  ");
    }

    Console.WriteLine();
}

Output:

Each line is a found subset, numbers in () are the original index of the number used in the subset

14(60) 3(107)
14(60) 3(109)
14(60) 3(102)
13(59) 4(105)
13(59) 4(111)
12(64) 5(96)
12(64) 5(104)
12(64) 5(112)
12(64) 5(110)
12(65) 5(96)
12(65) 5(104)
12(65) 5(112)
12(65) 5(110)
11(100) 6(108)
11(100) 6(113)
11(61) 6(108)
11(61) 6(113)
11(92) 6(108)
11(92) 6(113)
11(62) 6(108)
11(62) 6(113)
11(99) 6(108)
11(99) 6(113)
9(103) 8(93)
9(103) 8(94)
9(103) 8(97)
9(103) 8(98)
9(103) 8(101)
Subsets found: 28
00:00:00.0017020 (measured when no printing is performed)


The higher k is, the more cutoffs can be made. This is when you'll see the major performance difference. Your current code (the recursive version) also performs significantly slower when s is goes higher.

With k=5, s=60
Your current code: found 45070 subsets in 2.8602923 seconds
My code: found 45070 subsets in 0.0116727 seconds
That is 99.6% speed improvement

我以前的答案工作原理切断的组合的数量来检查。但一旦你对数组进行排序,这将显著提高。原则是相似的,但由于解决方案是完全不同的,我决定把它放在一个单独的答案。

我只小心使用.NET Framework 2的功能。可能会添加一个可视化的解释后,但评论应该是不够的。

class Puzzle
{
    private readonly int[] _tailSums;
    public readonly SubsetElement[] Elements;
    public readonly int N;

    public Puzzle(int[] numbers)
    {
        // Set N and make Elements array
        // (to remember the original index of each element)
        this.N = numbers.Length;
        this.Elements = new SubsetElement[this.N];

        for (var i = 0; i < this.N; i++)
        {
            this.Elements[i] = new SubsetElement(numbers[i], i);
        }

        // Sort Elements descendingly by their Number value
        Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number));

        // Save tail-sums to allow immediate access by index
        // Allow immedate calculation by index = N, to sum 0
        this._tailSums = new int[this.N + 1];
        var sum = 0;

        for (var i = this.N - 1; i >= 0; i--)
        {
            this._tailSums[i] = sum += this.Elements[i].Number;
        }
    }

    public void Solve(int s, Action<SubsetElement[]> callback)
    {
        for (var k = 1; k <= this.N; k++)
            this.Solve(k, s, callback);
    }

    public void Solve(int k, int s, Action<SubsetElement[]> callback)
    {
        this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback);
    }

    private void ScanSubsets(int startIndex, int k, int s,
                             List<SubsetElement> subset, Action<SubsetElement[]> cb)
    {
        // No more numbers to add, and current subset is guranteed to be valid
        if (k == 0)
        {
            // Callback with current subset
            cb(subset.ToArray());
            return;
        }

        // Sum the smallest k elements
        var minSubsetStartIndex = this.N - k;
        var minSum = this._tailSums[minSubssetStartIndex];

        // Smallest possible sum is greater than wanted sum,
        // so a valid subset cannot be found
        if (minSum > s)
        {
            return;
        }

        // Find largest number that satisfies the condition
        // that a valid subset can be found
        minSum -= this.Elements[minSubsetStartIndex].Number;

        // But remember the last index that satisfies the condition
        var minSubsetEndIndex = minSubsetStartIndex;

        while (minSubsetStartIndex > startIndex &&
               minSum + this.Elements[minSubsetStartIndex - 1].Number <= s)
        {
            minSubsetStartIndex--;
        }

        // Find the first number in the sorted sequence that is
        // the largest number we just found (in case of duplicates)
        while (minSubsetStartIndex > startIndex &&
               Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1])
        {
            minSubsetStartIndex--;
        }

        // [minSubsetStartIndex .. maxSubsetEndIndex] is the
        // full range we must check in recursion

        for (var subsetStartIndex = minSubsetStartIndex;
             subsetStartIndex <= minSubsetEndIndex;
             subsetStartIndex++)
        {
            // Find the largest possible sum, which is the sum of the
            // k first elements, starting at current subsetStartIndex
            var maxSum = this._tailSums[subsetStartIndex] -
                         this._tailSums[subsetStartIndex + k];

            // The largest possible sum is less than the wanted sum,
            // so a valid subset cannot be found
            if (maxSum < s)
            {
                return;
            }

            // Add current number to the subset
            var x = this.Elements[subsetStartIndex];
            subset.Add(x);

            // Recurse through the sub-problem to the right
            this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb);

            // Remove current number and continue loop
            subset.RemoveAt(subset.Count - 1);
        }
    }

    public sealed class SubsetElement
    {
        public readonly int Number;
        public readonly int Index;

        public SubsetElement(int number, int index)
        {
            this.Number = number;
            this.Index = index;
        }

        public override string ToString()
        {
            return string.Format("{0}({1})", this.Number, this.Index);
        }
    }
}

使用和性能测试:

private static void Main()
{
    var sw = Stopwatch.StartNew();
    var puzzle = new Puzzle(new[]
        {
            7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
            123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
            112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
            34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
            54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
            60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
            14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
            28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
            29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
            15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
            11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
            5, 4, 5, 6
        });

    puzzle.Solve(2, 17, PuzzleOnSubsetFound);

    sw.Stop();
    Console.WriteLine("Subsets found: " + _subsetsCount);
    Console.WriteLine(sw.Elapsed);
}

private static int _subsetsCount;

private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset)
{
    _subsetsCount++;
    return; // Skip prints when speed-testing

    foreach (var el in subset)
    {
        Console.Write(el.ToString());
        Console.Write("  ");
    }

    Console.WriteLine();
}

输出:

每个行是一个被发现的子集,在()中的数字是子集中使用的数字的原始索引

14(60) 3(107)
14(60) 3(109)
14(60) 3(102)
13(59) 4(105)
13(59) 4(111)
12(64) 5(96)
12(64) 5(104)
12(64) 5(112)
12(64) 5(110)
12(65) 5(96)
12(65) 5(104)
12(65) 5(112)
12(65) 5(110)
11(100) 6(108)
11(100) 6(113)
11(61) 6(108)
11(61) 6(113)
11(92) 6(108)
11(92) 6(113)
11(62) 6(108)
11(62) 6(113)
11(99) 6(108)
11(99) 6(113)
9(103) 8(93)
9(103) 8(94)
9(103) 8(97)
9(103) 8(98)
9(103) 8(101)
Subsets found: 28
00:00:00.0017020 (measured when no printing is performed)


高K值,更可。这是当你会看到主要性能差异。您的当前代码(递归版本)也执行显着慢时,S是去更高。

With k=5, s=60
Your current code: found 45070 subsets in 2.8602923 seconds
My code: found 45070 subsets in 0.0116727 seconds
That is 99.6% speed improvement

answer2: 回答2:

Simply search for all combinations of size K, and check each if it satisfies the condition.

The fastest algorithm for k combinations, suiting your case, would be:

for (var i1 = 0; i1 <= n; i1++)
{
    for (var i2 = i1 + 1; i2 <= n; i2++)
    {
        for (var i3 = i2 + 1; i3 <= n; i3++)
        {
            ...

            for (var ik = iOneBeforeK + 1; ik <= n; ik++)
            {
                if (arr[i1] + arr[i2] + ... + arr[ik] == sum)
                {
                    // this is a valid subset
                }
            }
        }
    }
}

But you are talking about numbers and summing them up, meaning you could make cutoffs with a smarter algorithm.

Since all numbers are positive, you know that if a single number is big enough, you cannot add to it any more positive numbers and have it sum up to s. Given s=6 and k=4, the highest number to include in the search is s-k+1=3. 3+1+1+1 is k numbers, 1 being your lowest possible number, sums up to 6. Any number above 3 couldn't have 3 other positives added to it, and have the sum <= 6.

But wait, your minimum possible value isn't 1, it is 3. That's even better. So assume k=10, n=60,

只需搜索大小k的所有组合,并检查是否满足条件。

K组合的最快的算法,适合你的情况,会:

for (var i1 = 0; i1 <= n; i1++)
{
    for (var i2 = i1 + 1; i2 <= n; i2++)
    {
        for (var i3 = i2 + 1; i3 <= n; i3++)
        {
            ...

            for (var ik = iOneBeforeK + 1; ik <= n; ik++)
            {
                if (arr[i1] + arr[i2] + ... + arr[ik] == sum)
                {
                    // this is a valid subset
                }
            }
        }
    }
}

但你所说的数字和总结起来,这意味着你可以用一个更聪明的算法使保险丝。

因为所有的数字都是积极的,你知道,如果一个数量足够大的话,你不能给它添加任何正数,它总结了美国S = 6和K = 4,包括在搜索次数最多的是S-K + 1 = 3。3 + 1 + 1 + 1是K数,1是你的最低可能的数目,总结多达6。任何数字以上3不能有其他3个积极的补充,并有总和;LT = = 6。

但是等等,你的最小可能值不是1,是3。那更好。所以假设k = 10,N = 60,

c#  algorithm  .net-2.0  dynamic-programming  subset-sum