找出加起来等于给定数的数的子集
本文关键字：子集 起来 | 更新日期: 2023-09-27 18:13:51
我有一个问题，我需要使用c#来解决。有一个十进制数字数组(表示仓库在不同时间收到的物品数量)。这个数组已经按照收到数量的顺序进行了排序。我需要能够找到最早的数量组合，这些数量总和为指定的总数量。
例如，假设我有一些数量按时间顺序排列如下[13,6,9,8,23,18,4]，并且假设我要匹配的总数量是23。那么我应该能够得到[13,6,4]作为匹配子集，尽管[6,9,8]和[23]也匹配，但不是最早的。
最好的方法/算法是什么?
到目前为止，我已经提出了一个使用递归的相当朴素的方法。
public class MatchSubset
{
private decimal[] qty = null;
private decimal matchSum = 0;
public int operations = 0;
public int[] matchedIndices = null;
public int matchCount = 0;
private bool SumUp(int i, int n, decimal sum)
{
operations++;
matchedIndices[matchCount++] = i;
sum += qty[i];
if (sum == matchSum)
return true;
if (i >= n - 1)
{
matchCount--;
return false;
}
if (SumUp(i + 1, n, sum))
return true;
sum -= qty[i];
matchCount--;
return SumUp(i + 1, n, sum);
}
public bool Match(decimal[] qty, decimal matchSum)
{
this.qty = qty;
this.matchSum = matchSum;
matchCount = 0;
matchedIndices = new int[qty.Count()];
return SumUp(0, qty.Count(), 0);
}
}
static void Main(string[] args)
{
var match = new MatchSubset();
int maxQtys = 20;
Random rand = new Random(DateTime.Now.Millisecond);
decimal[] qty = new decimal[maxQtys];
for (int i = 0; i < maxQtys - 2; i++)
qty[i] = rand.Next(1, 500);
qty[maxQtys - 2] = 99910;
qty[maxQtys - 1] = 77910;
DateTime t1 = DateTime.Now;
if (match.Match(qty, 177820))
{
Console.WriteLine(DateTime.Now.Subtract(t1).TotalMilliseconds);
Console.WriteLine("Operations: " + match.operations);
for (int i = 0; i < match.matchCount; i++)
{
Console.WriteLine(match.matchedIndices[i]);
}
}
}
匹配子集可以短于一个元素，长于原始集合(包含所有元素)。但是为了测试最坏的情况，在我的测试程序中，我使用了一个任意长的集合，其中只有最后两个与给定的数字匹配。
我看到集合中有20个数字，它调用递归函数超过一百万次，最大递归深度为20。如果我在生产中遇到一组30个或更多的数字，我担心它会消耗很长时间。
是否有进一步优化的方法?还有，看看那些不喜欢的人，这是问这类问题的错误地方吗?
我无法以革命性的东西结束，所以所呈现的解决方案只是相同的暴力破解算法的不同实现，具有2个优化。第一个优化是使用迭代实现而不是递归实现。我不认为这很重要，因为您更有可能以时间不足而不是堆栈空间不足而告终，但总的来说，这仍然是一个很好的方法，并且不难实现。最重要的是第二个。其思想是，在"前进"步骤中，只要当前和大于目标和，就可以跳过检查与当前项值大于或等于的下一项。通常这是通过首先对输入集进行排序来完成的，这在您的情况下并不适用。然而，在考虑如何克服这个限制时，我意识到我所需要的只是为每个项目提供下一个值小于该项目值的项目的索引，这样我就可以跳转到该索引，直到我到达末尾。
现在，尽管在最坏的情况下，两种实现都以相同的方式执行，即可能不会在合理的时间内结束，但在许多实际场景中，优化的变体能够非常快地产生结果，而原始版本仍然不能在合理的时间内结束。您可以通过使用maxQtys和maxQty参数来检查差异。
using System;
using System.Diagnostics;
using System.Linq;
namespace Tests
{
class Program
{
private static void Match(decimal[] inputQty, decimal matchSum, out int[] matchedIndices, out int matchCount, out int operations)
{
matchedIndices = new int[inputQty.Length];
matchCount = 0;
operations = 0;
var nextLessQtyPos = new int[inputQty.Length];
for (int i = inputQty.Length - 1; i >= 0; i--)
{
var currentQty = inputQty[i];
int nextPos = i + 1;
while (nextPos < inputQty.Length)
{
var nextQty = inputQty[nextPos];
int compare = nextQty.CompareTo(currentQty);
if (compare < 0) break;
nextPos = nextLessQtyPos[nextPos];
if (compare == 0) break;
}
nextLessQtyPos[i] = nextPos;
}
decimal currentSum = 0;
for (int nextPos = 0; ;)
{
if (nextPos < inputQty.Length)
{
// Forward
operations++;
var nextSum = currentSum + inputQty[nextPos];
int compare = nextSum.CompareTo(matchSum);
if (compare < 0)
{
matchedIndices[matchCount++] = nextPos;
currentSum = nextSum;
nextPos++;
}
else if (compare > 0)
{
nextPos = nextLessQtyPos[nextPos];
}
else
{
// Found
matchedIndices[matchCount++] = nextPos;
break;
}
}
else
{
// Backward
if (matchCount == 0) break;
var lastPos = matchedIndices[--matchCount];
currentSum -= inputQty[lastPos];
nextPos = lastPos + 1;
}
}
}
public class MatchSubset
{
private decimal[] qty = null;
private decimal matchSum = 0;
public int operations = 0;
public int[] matchedIndices = null;
public int matchCount = 0;
private bool SumUp(int i, int n, decimal sum)
{
operations++;
matchedIndices[matchCount++] = i;
sum += qty[i];
if (sum == matchSum)
return true;
if (i >= n - 1)
{
matchCount--;
return false;
}
if (SumUp(i + 1, n, sum))
return true;
sum -= qty[i];
matchCount--;
return SumUp(i + 1, n, sum);
}
public bool Match(decimal[] qty, decimal matchSum)
{
this.qty = qty;
this.matchSum = matchSum;
matchCount = 0;
matchedIndices = new int[qty.Count()];
return SumUp(0, qty.Count(), 0);
}
}
static void Main(string[] args)
{
int maxQtys = 3000;
decimal matchQty = 177820;
var qty = new decimal[maxQtys];
int maxQty = (int)(0.5m * matchQty);
var random = new Random();
for (int i = 0; i < maxQtys - 2; i++)
qty[i] = random.Next(1, maxQty);
qty[maxQtys - 2] = 99910;
qty[maxQtys - 1] = 77910;
Console.WriteLine("Source: {" + string.Join(", ", qty.Select(v => v.ToString())) + "}");
Console.WriteLine("Target: {" + matchQty + "}");
int[] matchedIndices;
int matchCount;
int operations;
var sw = new Stopwatch();
Console.Write("#1 processing...");
sw.Restart();
Match(qty, matchQty, out matchedIndices, out matchCount, out operations);
sw.Stop();
ShowResult(matchedIndices, matchCount, operations, sw.Elapsed);
Console.Write("#2 processing...");
var match = new MatchSubset();
sw.Restart();
match.Match(qty, matchQty);
sw.Stop();
ShowResult(match.matchedIndices, match.matchCount, match.operations, sw.Elapsed);
Console.Write("Done.");
Console.ReadLine();
}
static void ShowResult(int[] matchedIndices, int matchCount, int operations, TimeSpan time)
{
Console.WriteLine();
Console.WriteLine("Time: " + time);
Console.WriteLine("Operations: " + operations);
if (matchCount == 0)
Console.WriteLine("No Match.");
else
Console.WriteLine("Match: {" + string.Join(", ", Enumerable.Range(0, matchCount).Select(i => matchedIndices[i].ToString())) + "}");
}
}
}