找到所有 k 大小的子集，其中包含 n 大小的重复未排序正整数袋的总和 s
Find all k-size subsets with sum s of an n-size bag of duplicate unsorted positive integers
请注意，这是 C# .NET 2.0 项目所必需的（Linq 不允许）。
我知道这里已经提出了非常相似的问题，并且我已经生成了一些工作代码（见下文），但仍然希望获得有关如何在给定 k 和 s 条件下使算法更快的建议。
这是我到目前为止学到的：
动态规划是找到一个（不是所有）子集的最有效方法。如果我错了，请纠正我。有没有一种方法可以重复调用 DP 代码来生成更新的子集，直到袋子（重复设置）用完？
如果没有，那么有没有一种方法可以加速我下面的回溯递归算法，它确实产生了我需要的东西，但我认为在 O(2^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 限制为最大 2-3GB 但时间应该是 O(n^something) 而不是
(某物^n).
包包不得整理，重复不得删除
结果应该是匹配中数字的索引
子集，而不是数字本身（因为我们有重复项）。
动态编程尝试
这是根据 whosebug.com 上类似问题的答案改编的 C# 动态编程版本：
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# 递归编程版本，改编自 whosebug.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 的子集，如果我可以重复调用它，那么每次调用都会 returns 不同的子集，直到没有更多匹配的子集。
另外我不知道在哪里初始化DP算法的备忘录。我在访问任何方法时自动运行的静态构造函数中完成了它。这是正确的初始化位置还是需要将其移至 FindSunset() 方法内部 [注释掉]？
至于递归版本，是回溯吗？我们怎样才能加快速度。它工作正常并考虑了 k 和 s 但完全没有效率。
让我们将此线程作为所有 C# SubsetSum 相关问题的源头！
只需搜索所有尺寸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。给定 s=6 和 k=4，要包含在搜索中的最大数字是 s-k+1=3。 3+1+1+1 是 k 个数字，1 是您可能的最小数字，总和为 6。任何大于 3 的数字都不能添加 3 个其他正数，并且总和 <= 6.
但是等等，您的最小可能值不是 1，而是 3。那更好。所以假设 k=10、n=60、min=3。 "highest number scenario" 是 x+min(k-1)=n -> x=60-3*9=33。所以要考虑的最高数字是 33.
这减少了数组中要考虑的相关数字的数量，因此减少了要查找的组合的数量。
但它变得更好了。假设 k=10、n=60、min=3。数组中的第一个数字恰好是 20，因此它是相关的，应该进行检查。让我们找到包含 20:
的相关子集
一个新的 "puzzle" 出现了！ k=10-1、n=60-20、min=3。您现在可以从子谜题中截断许多数字，并在每一步中不断截断。
这可以通过计算子谜题中 k-1 个最低数字的平均值并将其用作 min.
来进一步改进
可以通过预先计算 k 子谜题 [0..n] 中的最低平均数和 k-1 子谜题 [1..n] 中的最低平均数，以及k-2 子谜题中的最低平均数 [2..n] 等等，并使用它们而不是在每个子谜题评估中一次又一次地重新计算相同的东西。
尝试使用下面的代码。对不起，我没有时间优化代码。您可以比较所有的方法，并得出更快的结论，不要忘记分享结果。
C#（您可以尝试从 List 中删除它可能会给您带来性能提升：
public static IEnumerable<List<int>> findSubsetsWithLengthKAndSumS2(Tuple<int, int> ks, List<int> set, List<int> subSet, List<int> subSetIndex)
{
if (ks.Item1 == 0 && ks.Item2 == 0)
{
var res = new List<List<int>>();
res.Add(subSetIndex);
return res;
}
else if (ks.Item1 > 0 && ks.Item2 > 0)
{
var res = set.Select((x, i) =>
{
var newSubset = subSet.Select(y => y).ToList();
newSubset.Add(x);
var newSubsetIndex = subSetIndex.Select(y => y).ToList();
newSubsetIndex.Add(i);
var newSet = set.Skip(i).ToList();
return findSubsetsWithLengthKAndSumS2(Tuple.Create(ks.Item1 - 1, ks.Item2 - x), newSet, newSubset, newSubsetIndex).ToList();
}
).SelectMany(x => x).ToList();
return res;
}
else
return new List<List<int>>();
}
...
var res = findSubsetsWithLengthKAndSumS2(Tuple.Create(2, 293), numbers.ToList(), new List<int>(), new List<int>());
F#（我添加它只是为了好玩=），它也没有优化，我认为代码中最慢的地方是'skip'）：
let skip (list:List<int>) index =
list |> List.mapi (fun i x -> if i > index then Some(x) else None) |> List.filter (fun x -> x.IsSome) |> List.map (fun x -> x.Value)
let rec findSubsetsWithLengthKAndSumS (ks:int*int) (set:list<int>) (subSet:list<int>) =
[
match ks with
|0,0 -> yield subSet
| x,y when x > 0 && y > 0 -> yield! set |> List.mapi (fun i x-> findSubsetsWithLengthKAndSumS ((fst ks)-1,(snd ks)-x) (skip set i ) (x::subSet)) |> Seq.concat
| _,_-> yield []
]
...
let res = Subsets.findSubsetsWithLengthKAndSumS (2,293) numbers [] |> List.filter (fun x-> x.Length >0)
我相信这个迭代版本在很多时候都会比其他版本更快。它使用 .net 2.0:
public delegate IEnumerable< IEnumerable< int > > findSubset();
public delegate bool findSubsetsIterativeFilter( int[] sourceSet, int[] indiciesToSum, int expected );
public static bool Summ( int[] sourceSet, int[] indicies, int expected )
{
var sum = 0;
for( int i = 0; i < indicies.Length; i++ )
sum += sourceSet[ indicies[ i ] ];
return sum == expected;
}
public static IEnumerable< IEnumerable< int > > findSubsetsIterative( int k, int[] sourceSet, findSubsetsIterativeFilter specialCondition, int expected )
{
var a = new int[ k ];
for( int i = 0; i < k; i++ )
a[ i ] = i;
var p = k - 1;
while( p >= 0 )
{
if( specialCondition( sourceSet, a, expected ) )
yield return ( int[] )a.Clone();
p = ( a[ k - 1 ] == sourceSet.Length - 1 ) ? p - 1 : k - 1;
if( p >= 0 )
for( int i = k - 1; i >= p; i-- )
a[ i ] = a[ p ] + i - p + 1;
}
}
...
findSubsetsIterative( 2, a, Summ, 293 );
我测量了我的代码和 Yorye 的代码，这就是我得到的。我的代码速度提高了 4-10 倍。您是否在实验中使用了我的答案中的 'findSubsetsIterative'？
findSubsetsIterative( 4, GenerateSOurceData(1), Summ, 400 ) Elapsed:
00:00:00.0012113 puzzle.Solve(4, 400, PuzzleOnSubsetFound) Elapsed:
00:00:00.0046170
findSubsetsIterative( 5, GenerateSOurceData(1), Summ, 60 ) Elapsed:
00:00:00.0012960 puzzle.Solve(5, 60, PuzzleOnSubsetFound) Elapsed:
00:00:00.0108568
Here i increased incoming array in 5x (just copied array 5 times into new big array):
findSubsetsIterative( 5, GenerateSOurceData(5), Summ, 60 )
Elapsed: 00:00:00.0013067
puzzle.Solve(5, 60, PuzzleOnSubsetFound)
Elapsed: 00:00:21.3520840
我之前的回答是按照砍掉要检查的组合数的原则工作的。但是一旦你对数组进行排序，这就可以得到显着改善。原理差不多，但是解决方法完全不同，所以我决定放在一个单独的答案中。
我小心翼翼地只使用 .Net Framework 2.0 功能。稍后可能会添加视觉解释，但评论应该足够了。
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
可以用和背包问题类似的解法来解决
dp[i][j][k]=使用前“i”个元素总和等于 j 的 k 大小子集的数量
dp[i][j][k]=dp[i-1][j][k] + dp[i-1][j-a[i]][k-1]
是dp的更新（使用第i个元素或不使用它）
for(int i=0;i<=n;i++) dp[i][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=w;j++){
for(int k=1;k<=i;k++){
dp[i][j][k]=dp[i-1][j][k] ;
if(j>=a[i-1]){
dp[i][j][k]+=dp[i-1][j-a[i-1]][k-1];
}
}
}
}
有多种解决方案，但没有人展示如何使用动态规划找到答案。
关键是使用动态规划来建立一个数据结构，以后可以从中找到所有的解决方案。
除了请求的函数，我收集了关于有多少解决方案的信息，并将FindSolution(node, position)写到return位置position以[=13=开头的解决方案] 不计算其余部分。如果您想要所有这些，使用该功能将是低效的。但是，例如，使用此函数可以计算出将 10000 表示为 20 个质数之和的第十亿种方式。这对于给出的其他方法是不可行的。
using System;
using System.Collections.Generic;
public class SubsetSum
{
public class SolutionNode<T>
{
// The index we found the value at
public int Index {get; set;}
// The value we add for this solution
public T Value {get; set;}
// How many solutions we have found.
public int Count {get; set;}
// The rest of this solution.
public SolutionNode<T> Tail {get; set;}
// The next solution.
public SolutionNode<T> Next {get; set;}
}
// This uses dynamic programming to create a summary of all solutions.
public static SolutionNode<int> FindSolution(int[] numbers, int target, int subsetSize)
{
// By how many are in our list, by what they sum to, what SolutionNode<int> has our answer?
List<Dictionary<int, SolutionNode<int>>> solutionOf = new List<Dictionary<int, SolutionNode<int>>>();
// Initialize empty solutions.
for (int i = 0; i <= subsetSize; i++)
{
solutionOf.Add(new Dictionary<int, SolutionNode<int>>());
}
// We discover from the last number in the list forward.
// So discovering from the last index forward makes them ordered.
for (int i = numbers.Length - 1; -1 < i; i--)
{
int number = numbers[i];
// Descending here so we don't touch solutionOf[j-1] until after we have solutionOf[j] updated.
for (int j = subsetSize; 0 < j; j--)
{
// All previously found sums with j entries
Dictionary<int, SolutionNode<int>> after = solutionOf[j];
// All previously found sums with j-1 entries
Dictionary<int, SolutionNode<int>> before = solutionOf[j-1];
foreach (KeyValuePair<int, SolutionNode<int>> pair in before)
{
SolutionNode<int> newSolution = new SolutionNode<int>();
int newSum = pair.Key + number;
newSolution.Index = i;
newSolution.Value = number;
newSolution.Count = pair.Value.Count;
newSolution.Tail = pair.Value;
if (after.ContainsKey(newSum))
{
newSolution.Next = after[newSum];
newSolution.Count = pair.Value.Count + after[newSum].Count;
}
after[newSum] = newSolution;
}
// And special case empty set.
if (1 == j)
{
SolutionNode<int> newSolution = new SolutionNode<int>();
newSolution.Index = i;
newSolution.Value = number;
newSolution.Count = 1;
if (after.ContainsKey(number))
{
newSolution.Next = after[number];
newSolution.Count = after[number].Count;
}
after[number] = newSolution;
}
}
}
// Return what we found.
try
{
return solutionOf[subsetSize][target];
}
catch
{
throw new Exception("No solutions found");
}
}
// The function we were asked for.
public static IEnumerable<List<int>> ListSolutions (SolutionNode<int> node)
{
List<int> solution = new List<int>();
List<SolutionNode<int>> solutionPath = new List<SolutionNode<int>>();
// Initialize with starting information.
solution.Add(0); // This will be removed when we get node
solutionPath.Add(node); // This will be our start.
while (0 < solutionPath.Count)
{
// Erase the tail of our previous solution
solution.RemoveAt(solution.Count - 1);
// Pick up our next.
SolutionNode<int> current = solutionPath[solutionPath.Count - 1];
solutionPath.RemoveAt(solutionPath.Count - 1);
while (current != null)
{
solution.Add(current.Index);
solutionPath.Add(current.Next);
if (current.Tail == null)
{
yield return solution;
}
current = current.Tail;
}
}
}
// And for fun, a function that dynamic programming makes easy - return any one of them!
public static List<int> FindSolution(SolutionNode<int> node, int position)
{
// Switch to counting from the end.
position = node.Count - position - 1;
List<int> solution = new List<int>();
while (node != null)
{
while (node.Next != null && position < node.Next.Count)
{
node = node.Next;
}
solution.Add(node.Index);
node = node.Tail;
}
return solution;
}
public static void Main(string[] args)
{
SolutionNode<int> solution = FindSolution(
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}
, 400, 4);
IEnumerable<List<int>> listing = ListSolutions(solution);
foreach (List<int> sum in listing)
{
Console.WriteLine ("solution {0}", string.Join(", ", sum.ToArray()));
}
}
}
顺便说一句，这是我第一次尝试编写 C#。这是......痛苦的冗长。
请注意，这是 C# .NET 2.0 项目所必需的（Linq 不允许）。
我知道这里已经提出了非常相似的问题，并且我已经生成了一些工作代码（见下文），但仍然希望获得有关如何在给定 k 和 s 条件下使算法更快的建议。
这是我到目前为止学到的： 动态规划是找到一个（不是所有）子集的最有效方法。如果我错了，请纠正我。有没有一种方法可以重复调用 DP 代码来生成更新的子集，直到袋子（重复设置）用完？
如果没有，那么有没有一种方法可以加速我下面的回溯递归算法，它确实产生了我需要的东西，但我认为在 O(2^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 限制为最大 2-3GB 但时间应该是 O(n^something) 而不是 (某物^n).
包包不得整理，重复不得删除
结果应该是匹配中数字的索引 子集，而不是数字本身（因为我们有重复项）。
动态编程尝试
这是根据 whosebug.com 上类似问题的答案改编的 C# 动态编程版本：
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# 递归编程版本，改编自 whosebug.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 的子集，如果我可以重复调用它，那么每次调用都会 returns 不同的子集，直到没有更多匹配的子集。
另外我不知道在哪里初始化DP算法的备忘录。我在访问任何方法时自动运行的静态构造函数中完成了它。这是正确的初始化位置还是需要将其移至 FindSunset() 方法内部 [注释掉]？
至于递归版本，是回溯吗？我们怎样才能加快速度。它工作正常并考虑了 k 和 s 但完全没有效率。
让我们将此线程作为所有 C# SubsetSum 相关问题的源头！
只需搜索所有尺寸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。给定 s=6 和 k=4，要包含在搜索中的最大数字是 s-k+1=3。 3+1+1+1 是 k 个数字，1 是您可能的最小数字，总和为 6。任何大于 3 的数字都不能添加 3 个其他正数，并且总和 <= 6.
但是等等，您的最小可能值不是 1，而是 3。那更好。所以假设 k=10、n=60、min=3。 "highest number scenario" 是 x+min(k-1)=n -> x=60-3*9=33。所以要考虑的最高数字是 33.
这减少了数组中要考虑的相关数字的数量，因此减少了要查找的组合的数量。
但它变得更好了。假设 k=10、n=60、min=3。数组中的第一个数字恰好是 20，因此它是相关的，应该进行检查。让我们找到包含 20:
的相关子集
一个新的 "puzzle" 出现了！ k=10-1、n=60-20、min=3。您现在可以从子谜题中截断许多数字，并在每一步中不断截断。
这可以通过计算子谜题中 k-1 个最低数字的平均值并将其用作 min.
可以通过预先计算 k 子谜题 [0..n] 中的最低平均数和 k-1 子谜题 [1..n] 中的最低平均数，以及k-2 子谜题中的最低平均数 [2..n] 等等，并使用它们而不是在每个子谜题评估中一次又一次地重新计算相同的东西。
尝试使用下面的代码。对不起，我没有时间优化代码。您可以比较所有的方法，并得出更快的结论，不要忘记分享结果。
C#（您可以尝试从 List 中删除它可能会给您带来性能提升：
public static IEnumerable<List<int>> findSubsetsWithLengthKAndSumS2(Tuple<int, int> ks, List<int> set, List<int> subSet, List<int> subSetIndex)
{
if (ks.Item1 == 0 && ks.Item2 == 0)
{
var res = new List<List<int>>();
res.Add(subSetIndex);
return res;
}
else if (ks.Item1 > 0 && ks.Item2 > 0)
{
var res = set.Select((x, i) =>
{
var newSubset = subSet.Select(y => y).ToList();
newSubset.Add(x);
var newSubsetIndex = subSetIndex.Select(y => y).ToList();
newSubsetIndex.Add(i);
var newSet = set.Skip(i).ToList();
return findSubsetsWithLengthKAndSumS2(Tuple.Create(ks.Item1 - 1, ks.Item2 - x), newSet, newSubset, newSubsetIndex).ToList();
}
).SelectMany(x => x).ToList();
return res;
}
else
return new List<List<int>>();
}
...
var res = findSubsetsWithLengthKAndSumS2(Tuple.Create(2, 293), numbers.ToList(), new List<int>(), new List<int>());
F#（我添加它只是为了好玩=），它也没有优化，我认为代码中最慢的地方是'skip'）：
let skip (list:List<int>) index =
list |> List.mapi (fun i x -> if i > index then Some(x) else None) |> List.filter (fun x -> x.IsSome) |> List.map (fun x -> x.Value)
let rec findSubsetsWithLengthKAndSumS (ks:int*int) (set:list<int>) (subSet:list<int>) =
[
match ks with
|0,0 -> yield subSet
| x,y when x > 0 && y > 0 -> yield! set |> List.mapi (fun i x-> findSubsetsWithLengthKAndSumS ((fst ks)-1,(snd ks)-x) (skip set i ) (x::subSet)) |> Seq.concat
| _,_-> yield []
]
...
let res = Subsets.findSubsetsWithLengthKAndSumS (2,293) numbers [] |> List.filter (fun x-> x.Length >0)
我相信这个迭代版本在很多时候都会比其他版本更快。它使用 .net 2.0:
public delegate IEnumerable< IEnumerable< int > > findSubset();
public delegate bool findSubsetsIterativeFilter( int[] sourceSet, int[] indiciesToSum, int expected );
public static bool Summ( int[] sourceSet, int[] indicies, int expected )
{
var sum = 0;
for( int i = 0; i < indicies.Length; i++ )
sum += sourceSet[ indicies[ i ] ];
return sum == expected;
}
public static IEnumerable< IEnumerable< int > > findSubsetsIterative( int k, int[] sourceSet, findSubsetsIterativeFilter specialCondition, int expected )
{
var a = new int[ k ];
for( int i = 0; i < k; i++ )
a[ i ] = i;
var p = k - 1;
while( p >= 0 )
{
if( specialCondition( sourceSet, a, expected ) )
yield return ( int[] )a.Clone();
p = ( a[ k - 1 ] == sourceSet.Length - 1 ) ? p - 1 : k - 1;
if( p >= 0 )
for( int i = k - 1; i >= p; i-- )
a[ i ] = a[ p ] + i - p + 1;
}
}
...
findSubsetsIterative( 2, a, Summ, 293 );
我测量了我的代码和 Yorye 的代码，这就是我得到的。我的代码速度提高了 4-10 倍。您是否在实验中使用了我的答案中的 'findSubsetsIterative'？
findSubsetsIterative( 4, GenerateSOurceData(1), Summ, 400 ) Elapsed: 00:00:00.0012113 puzzle.Solve(4, 400, PuzzleOnSubsetFound) Elapsed: 00:00:00.0046170
findSubsetsIterative( 5, GenerateSOurceData(1), Summ, 60 ) Elapsed: 00:00:00.0012960 puzzle.Solve(5, 60, PuzzleOnSubsetFound) Elapsed: 00:00:00.0108568
Here i increased incoming array in 5x (just copied array 5 times into new big array): findSubsetsIterative( 5, GenerateSOurceData(5), Summ, 60 ) Elapsed: 00:00:00.0013067 puzzle.Solve(5, 60, PuzzleOnSubsetFound) Elapsed: 00:00:21.3520840
我之前的回答是按照砍掉要检查的组合数的原则工作的。但是一旦你对数组进行排序，这就可以得到显着改善。原理差不多，但是解决方法完全不同，所以我决定放在一个单独的答案中。
我小心翼翼地只使用 .Net Framework 2.0 功能。稍后可能会添加视觉解释，但评论应该足够了。
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
可以用和背包问题类似的解法来解决
dp[i][j][k]=使用前“i”个元素总和等于 j 的 k 大小子集的数量
dp[i][j][k]=dp[i-1][j][k] + dp[i-1][j-a[i]][k-1]
是dp的更新（使用第i个元素或不使用它）
for(int i=0;i<=n;i++) dp[i][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=w;j++){
for(int k=1;k<=i;k++){
dp[i][j][k]=dp[i-1][j][k] ;
if(j>=a[i-1]){
dp[i][j][k]+=dp[i-1][j-a[i-1]][k-1];
}
}
}
}
有多种解决方案，但没有人展示如何使用动态规划找到答案。
关键是使用动态规划来建立一个数据结构，以后可以从中找到所有的解决方案。
除了请求的函数，我收集了关于有多少解决方案的信息，并将FindSolution(node, position)写到return位置position以[=13=开头的解决方案] 不计算其余部分。如果您想要所有这些，使用该功能将是低效的。但是，例如，使用此函数可以计算出将 10000 表示为 20 个质数之和的第十亿种方式。这对于给出的其他方法是不可行的。
using System;
using System.Collections.Generic;
public class SubsetSum
{
public class SolutionNode<T>
{
// The index we found the value at
public int Index {get; set;}
// The value we add for this solution
public T Value {get; set;}
// How many solutions we have found.
public int Count {get; set;}
// The rest of this solution.
public SolutionNode<T> Tail {get; set;}
// The next solution.
public SolutionNode<T> Next {get; set;}
}
// This uses dynamic programming to create a summary of all solutions.
public static SolutionNode<int> FindSolution(int[] numbers, int target, int subsetSize)
{
// By how many are in our list, by what they sum to, what SolutionNode<int> has our answer?
List<Dictionary<int, SolutionNode<int>>> solutionOf = new List<Dictionary<int, SolutionNode<int>>>();
// Initialize empty solutions.
for (int i = 0; i <= subsetSize; i++)
{
solutionOf.Add(new Dictionary<int, SolutionNode<int>>());
}
// We discover from the last number in the list forward.
// So discovering from the last index forward makes them ordered.
for (int i = numbers.Length - 1; -1 < i; i--)
{
int number = numbers[i];
// Descending here so we don't touch solutionOf[j-1] until after we have solutionOf[j] updated.
for (int j = subsetSize; 0 < j; j--)
{
// All previously found sums with j entries
Dictionary<int, SolutionNode<int>> after = solutionOf[j];
// All previously found sums with j-1 entries
Dictionary<int, SolutionNode<int>> before = solutionOf[j-1];
foreach (KeyValuePair<int, SolutionNode<int>> pair in before)
{
SolutionNode<int> newSolution = new SolutionNode<int>();
int newSum = pair.Key + number;
newSolution.Index = i;
newSolution.Value = number;
newSolution.Count = pair.Value.Count;
newSolution.Tail = pair.Value;
if (after.ContainsKey(newSum))
{
newSolution.Next = after[newSum];
newSolution.Count = pair.Value.Count + after[newSum].Count;
}
after[newSum] = newSolution;
}
// And special case empty set.
if (1 == j)
{
SolutionNode<int> newSolution = new SolutionNode<int>();
newSolution.Index = i;
newSolution.Value = number;
newSolution.Count = 1;
if (after.ContainsKey(number))
{
newSolution.Next = after[number];
newSolution.Count = after[number].Count;
}
after[number] = newSolution;
}
}
}
// Return what we found.
try
{
return solutionOf[subsetSize][target];
}
catch
{
throw new Exception("No solutions found");
}
}
// The function we were asked for.
public static IEnumerable<List<int>> ListSolutions (SolutionNode<int> node)
{
List<int> solution = new List<int>();
List<SolutionNode<int>> solutionPath = new List<SolutionNode<int>>();
// Initialize with starting information.
solution.Add(0); // This will be removed when we get node
solutionPath.Add(node); // This will be our start.
while (0 < solutionPath.Count)
{
// Erase the tail of our previous solution
solution.RemoveAt(solution.Count - 1);
// Pick up our next.
SolutionNode<int> current = solutionPath[solutionPath.Count - 1];
solutionPath.RemoveAt(solutionPath.Count - 1);
while (current != null)
{
solution.Add(current.Index);
solutionPath.Add(current.Next);
if (current.Tail == null)
{
yield return solution;
}
current = current.Tail;
}
}
}
// And for fun, a function that dynamic programming makes easy - return any one of them!
public static List<int> FindSolution(SolutionNode<int> node, int position)
{
// Switch to counting from the end.
position = node.Count - position - 1;
List<int> solution = new List<int>();
while (node != null)
{
while (node.Next != null && position < node.Next.Count)
{
node = node.Next;
}
solution.Add(node.Index);
node = node.Tail;
}
return solution;
}
public static void Main(string[] args)
{
SolutionNode<int> solution = FindSolution(
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}
, 400, 4);
IEnumerable<List<int>> listing = ListSolutions(solution);
foreach (List<int> sum in listing)
{
Console.WriteLine ("solution {0}", string.Join(", ", sum.ToArray()));
}
}
}
顺便说一句，这是我第一次尝试编写 C#。这是......痛苦的冗长。