高效生成总和在指定范围内的所有组合(在所有深度)

Question

我有一组 80 个数字，我想找到总计到给定数字的组合列表。下面的代码工作正常，但它需要太长时间，有人可以帮我一个增强的版本，可以更快地处理它吗？

public void sum_up(List<int> numbers, int target)    
{
sum_up_recursive(numbers, target, new List<int>());
}
public void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
int s = 0;
foreach (int x in partial) s += x;
if (s == target)
val +=" sum(" + string.Join(",", partial.ToArray()) + ")=" + target + Environment.NewLine;
if (s == target && string.Join(",", partial.ToArray()).Contains("130") &&
string.Join(",", partial.ToArray()).Contains("104"))
{
string gg = " sum(" + string.Join(",", partial.ToArray()) + ")=" + target;
val += " || || sum(" + string.Join(",", partial.ToArray()) + ")=" + target + Environment.NewLine;
}
if (s >= target)
return;
for (int i = 0; i < numbers.Count; i++)
{
List<int> remaining = new List<int>();
int n = numbers[i];
for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
List<int> partial_rec = new List<int>(partial);
partial_rec.Add(n);
sum_up_recursive(remaining, target, partial_rec);
}
lblResult.Text = val;                
}
private void btnCheck_Click(object sender, EventArgs e)
{
string[] vendorVal = txtvendor.Text.Split(',');
int[] myInts = Array.ConvertAll(vendorVal, s => int.Parse(s));
List<int> numbers = myInts.ToList();
int target = Convert.ToInt32(txtDifference.Text);
sum_up(numbers, target);
}

任何帮助不胜感激...

Answer 1

您一次又一次地重新计算相同的部分总和 - 此过程需要花费大量时间。如果 targer 和值合理并且您有足够的内存 - 请使用动态规划方法。

创建长度(TargetSum + 1)的数组A，其中包含中间和的可能变体列表。

对于每个项目值 V 使循环从总和S=TargetSum到V(反向遍历有助于避免重复使用同一项目)。如果条目A[S - V]不为空 - 将A[S - V]中的所有变体添加到A[V]中，并将V添加到 中。最后A[TargerSum]将包含所有可能的组合。

还要考虑memoization技术 - 它可能是由您的递归函数构造的 - 只需记住字典中的求和变体并重用存储的变体即可。