2

假设您有一组值（1, 1, 1, 12, 12, 16），您将如何生成总和在预定义范围内的所有可能组合（不重复）[min,max]。例如，以下是范围在13和之间的所有（所有深度的）组合17：

1 12

1 1 12

1 1 1 12

16

1 16

1 12这假设相同值的每个项目是无法区分的，因此您在最终输出中没有三个结果。蛮力是可能的，但在项目数量很大的情况下，所有深度的组合数量是天文数字。在上面的示例中，所有深度都有 (3 + 1) * (2 + 1) * (1 + 1) = 24 种组合。因此，总组合是任何给定值的项目数 + 1 的乘积。当然我们可以在逻辑上抛出部分和大于最大值的大量组合（例如，集合16 12已经大于最大值的值17，因此请跳过其中包含 a16和12的任何组合）。

我最初认为我可以将输入数组转换为两个数组并像里程表一样增加它们。但是我完全陷入了这种提前中断的递归算法上。有什么建议么？

{
    int uniqueValues = 3;
    int[] maxCounts = new int[uniqueValues];
    int[] values = new int[uniqueValues];

    // easy code to bin the data, just hardcoding for example
    maxCounts[0] = 3;
    values[0] = 1;
    maxCounts[1] = 2;
    values[1] = 12;
    maxCounts[2] = 1;
    values[2] = 16;

    GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}

private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    if (index >= maxValues.Length)
    {
        return;
    }

    while (currentCombo[index] < maxValues[index])
    {
        currentValue += values[index];

        if (currentValue> max)
        {                   
            return;
        }

        currentCombo[index]++;

        if (currentValue< min)
        {                    
            GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            results.Add((int[])currentCombo.Clone());
        }
    }
}

编辑

整数值仅用于演示。它可以是任何具有某种数值的对象（int、double、float等...）

通常只有少数唯一值（约 10 个左右），但可能有数千个项目。

4

5 回答 5

1

将主调用切换为：

GenerateCombinationsHelper2(new List<int[]>(), 13, 17, 0, maxCounts, new int[3], values);

然后添加此代码：

private void GenerateCombinationsHelper2(List<int[]> results, int min, int max, int index, int[] maxValues, int[] currentCombo, int[] values)
{
    int max_count = Math.Min((int)Math.Ceiling((double)max / values[index]), maxValues[index]);

    for(int count = 0; count <= max_count; count++)
    {
        currentCombo[index] = count;
        if(index < currentCombo.Length - 1)
        {
            GenerateCombinationsHelper2(results, min, max, index + 1, maxValues, currentCombo, values);
        }
        else
        {
            int sum = Sum(currentCombo, values);
            if(sum >= min && sum <= max)
            {
                int[] copy = new int[currentCombo.Length];
                Array.Copy(currentCombo, copy, copy.Length);
                results.Add(copy);
            }
        }
    }
}

private static int Sum(int[] combo, int[] values)
{
    int sum = 0;
    for(int i = 0; i < combo.Length; i++)
    {
        sum += combo[i] * values[i];
    }
    return sum;
}

它返回 5 个有效答案。

于 2013-10-10T03:50:16.407 回答
1

这类问题的总体趋势是，会出现的值相对较少，但每个值都会出现很多次。因此，您首先要创建一个数据结构，以有效地描述将加起来为所需值的组合，然后才能找出所有组合。（如果您知道“动态编程”一词，那正是我所描述的方法。）

C# 术语中显而易见的数据结构将是一个 Hashtable，其键是组合相加的总数，其值是列出最后一个元素位置的数组.

您如何构建该数据结构？

首先，您从一个包含总 0 作为键和一个空数组作为值的 Hashtable 开始。然后，对于数组的每个元素，您创建一个新总数列表，您可以从以前的总数中获得，并将元素的位置附加到它们的每个值（如果需要，插入一个新的）。当您浏览完所有元素后，您就有了数据结构。

现在，您可以仅搜索该数据结构中所需范围内的总数。对于每个这样的总数，您可以编写一个递归程序，该程序将遍历您的数据结构以产生组合。这一步确实可以产生组合爆炸，但令人高兴的是，产生的每个组合实际上都是您最终答案中的组合。所以如果这个阶段需要很长时间，那是因为你有很多最终的答案！

于 2013-10-10T04:35:44.377 回答
0

试试这个算法

int arr[] = {1,1,1,12,12,16}
for(int i = 0;i<2^arr.Length;i++)
{
int[] arrBin = BinaryFormat(i); // binary format i
for(int j = 0;j<arrBin.Length;j++)
  if (arrBin[j] == 1)
     Console.Write("{0} ", arr[j]);
Console.WriteLine();
}
于 2013-10-10T01:29:33.457 回答
0

这与恰好是NP-complete的子集和问题非常相似。

Wikipedia 对 NP 完全问题的描述如下：

尽管可以快速验证此类问题的任何给定解决方案，但首先没有已知的有效方法来找到解决方案。事实上，NP 完全问题最显着的特征是没有已知的快速解决方案。也就是说，使用任何当前已知的算法解决问题所需的时间会随着问题规模的增长而迅速增加。这意味着使用当今可用的任意数量的计算能力，解决其中许多问题的中等规模版本所需的时间很容易达到数十亿或数万亿年。因此，确定是否可以快速解决这些问题，称为 P 与 NP 问题，是当今计算机科学中主要的未解决问题之一。

如果确实有一种方法可以解决这个问题，除了暴力破解 powerset 并找到所有在给定范围内总和为一个值的子集，那么我会非常有兴趣听到它。

于 2013-10-10T01:53:11.997 回答
0

另一种实现的想法：

从数字列表创建一个堆栈列表，每个堆栈代表一个出现在列表中的数字，并且这个数字被压入堆栈的次数与他在数字列表中出现的次数一样多。更重要的是，这个列表是排序的。

这个想法是您遍历堆栈列表，在每个堆栈中，如果它不超过最大值，则一次弹出一个数字并调用函数，并执行跳过当前堆栈的附加调用。

该算法减少了许多冗余计算，例如当添加该值超过最大值时尝试添加具有相同值的不同元素。

我能够用这个算法解决相当大的问题（50 个数字或更多），具体取决于最小值和最大值，显然当间隔非常大时，组合的数量可能很大。

这是代码：

static void GenerateLimitedCombinations(List<int> intList, int minValue, int maxValue)
{
    intList.Sort();
    List<Stack<int>> StackList = new List<Stack<int>>();
    Stack<int> NewStack = new Stack<int>();
    NewStack.Push(intList[0]);
    StackList.Add(NewStack);

    for (int i = 1; i < intList.count; i++)
    {
        if (intList[i - 1] == intList[i])
            StackList[StackList.count - 1].Push(intList[i]);
        else
        {
            NewStack = new Stack<int>();
            NewStack.Push(intList[i]);
            StackList.Add(NewStack);
        }
    }

    GenerateLimitedCombinations(StackList, minValue, maxValue, 0, new List<int>(), 0);
}

static void GenerateLimitedCombinations(List<Stack<int>> stackList, int minValue, int maxValue, int currentStack, List<int> currentCombination, int currentSum)
{
    if (currentStack == stackList.count)
    {
        if (currentSum >= minValue)
        {
            foreach (int tempInt in CurrentCombination)
            {
                Console.Write(tempInt + " ");
            }
            Console.WriteLine(;
        }
    }

    else
    {
        int TempSum = currentSum;
        List<int> NewCombination = new List<int>(currentCombination);
        Stack<int> UndoStack = new Stack<int>();

        while (stackList[currentStack].Count != 0 && stackList[currentStack].Peek() + TempSum <= maxValue)
        {
            int AddedValue = stackList[currentStack].Pop();
            UndoStack.Push(AddedValue);
            NewCombination.Add(AddedValue);
            TempSum += AddedValue;
            GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, new List<int>(NewCombination), TempSum);
        }

        while (UndoStack.Count != 0)
        {
            stackList[currentStack].Push(UndoStack.Pop());
        }

        GenerateLimitedCombinations(stackList, minValue, maxValue, currentStack + 1, currentCombination, currentSum);
    }
}

这是一个测试程序：

static void Main(string[] args)
{
    Random Rnd = new Random();
    List<int> IntList = new List<int>();
    int NumberOfInts = 10, MinValue = 19, MaxValue 21;

    for (int i = 0; i < NumberOfInts; i++) { IntList.Add(Rnd.Next(1, 10));
    for (int i = 0; i < NumberOfInts; i++) { Console.Write(IntList[i] + " "); } Console.WriteLine(); Console.WriteLine();

    GenerateLimitedCombinations(IntList, MinValue, MaxValue);
    Console.ReadKey();
}
于 2013-10-13T14:47:14.097 回答