时间戳

首页 > 解决方案 > 如何获得一组数字的所有组合，这些组合将加起来或仅略超过一组数字？

c# - 如何获得一组数字的所有组合，这些组合将加起来或仅略超过一组数字？

问题描述

我正在尝试创建一个方法，该方法将获取一个整数列表并返回一个整数数组列表，其中包含总和为目标的所有数字组合。

例如，如果目标是 5 并且输入列表有

List<int> numbers = {1, 2, 3}

结果将是

List<int[]> resultNumbers = {[1,1,1,1,1], [1,1,1,2], [1,2,2], [1,1,3], [2,3]} etc.

我正在为我正在制作的应用程序编写此方法，但随后将代码移至控制台应用程序，以便我可以单独专注于它。我还想为数字与目标的接近程度添加容差，并将其计为添加到目标的一组数字。

List<int> numbers = new List<int>();
List<int> multipliers = new List<int>();
List<int[]> resultNumbers = new List<int[]>();
List<int> toFindAllSums = new List<int>();
List<int> toFindAllmultipliers = new List<int>();
List<int> toFindAllnumbers = new List<int>();
Random random = new Random();
int max = random.Next(20);
int target = 2000;

for (int i = 0; i < max; i++)
{
    int d = random.Next(200, 400);
    numbers.Add(d);
}

foreach (int i in numbers)
{
    int sum = 0;
    int iterations = 0;
    while (sum< 2000)
    {
        sum += i;
        iterations += 1;
        Console.Write(i + " + ");
        if (sum > 2000)
        {
            Console.WriteLine(" = " + sum);
            Console.Write("\n\t "+ iterations + "\n");
            multipliers.Add(iterations);
        }
    }
}

foreach (int i in numbers)
{
    int[] temp = new int[multipliers.ElementAt(numbers.IndexOf(i))];
    for (int j = 0; j < multipliers.ElementAt(numbers.IndexOf(i));  j++ )
    {
        temp[j] = i;
        toFindAllSums.Add(temp.Sum());
        toFindAllmultipliers.Add(j+1);
        toFindAllnumbers.Add(i);
    }
    resultNumbers.Add(temp);
}

Console.ReadLine();

这是自这个问题开始以来我更新的内容，我确实从中得到了很多结果，但我不确定它是否给了我所有可能的结果。

public List<int[]> FindAllSums(List<int> numbers, int target)
    {
        List<int> multipliers = new List<int>();
        List<int[]> resultNumbers = new List<int[]>();

        // find the maximum number of times a number int he given list can go into
        //the target and either equal or ecceed it (this could probably have been done using division)
        foreach (int i in numbers)
        {
            int sum = 0;
            int iterations = 0;
            while (sum < 2000)
            {
                sum += i;
                iterations += 1;
                if (sum > 2000)
                {
                    multipliers.Add(iterations);
                }
            }
        }

        //add those posibilites to the list of results.
        foreach (int i in numbers)
        {
            int[] temp = new int[multipliers.ElementAt(numbers.IndexOf(i))];
            for (int j = 0; j < multipliers.ElementAt(numbers.IndexOf(i)); j++)
            {
                temp[j] = i;
            }
            resultNumbers.Add(temp);
        }

        //since we know the maximum number of times each given number can go into the 
        //target we start creating arrays of numbers that will add to the target
        for (int i = 0; i < numbers.Count(); i++)
        {
            //create list because I like lists more than arrays
            List<int> tempList = new List<int>();

            //for all elements in the input list
            for (int k = 0; k < multipliers.ElementAt(i); k++)
            {
                //for the number of times the given number can go into the target
                for (int j1 = 0; j1 < numbers.Count(); j1++)
                {
                    //add that number to the list 
                    tempList.Add(numbers.ElementAt(i));
                    for (int j2 = 0; j2 < j1; j2++)
                    {
                        tempList.Add(numbers.ElementAt(i));

                    }                        
                    for (int j = j1; j < numbers.Count(); j++)
                    {
                        if (tempList.Sum() > 2000)
                        {
                            resultNumbers.Add(tempList.ToArray());
                            tempList.Clear();
                            break;
                        }
                        else
                        {
                            tempList.Add(numbers.ElementAt(j));
                        }
                    }
                }
            }
        }
        return resultNumbers;
    }

标签： c#algorithmlistmethodssum

解决方案

我尝试运行您的代码，然后 Visaul 工作室向我发送了“IndexOutofBoundsException”，我不太了解您的代码，但我想您的实现想法可能不正确。

这个问题不是动态规划的问题。

令 Cn 为目标数为 n 的结果，如果 n = 5，并且输入列表为 {1, 2, 3}，我们可以有下面的等式：

C5 = C1 x C4 + C2 x C3 + C3 x C2   (1)

如果 n = 6，则方程为：

C6 = C1 x C5 + C2 x C4 + C3 x C3   (2)

这里的“x”就像叉积一样，例如，我们可以很容易地计算出 C1 和 C2：

C1 = {{1}}

C2 = {{1, 1}, {2}}

因此

C1 x C2 = {{1, 1, 1}, {1, 2}}

而“+”表示联合，例如：

C2 x C3 + C3 x C2 = C2 x C3

因为 C2 x C3 = C3 X C2

对于实现，我们可以创建一个覆盖运算符“x”和“+”的类：

class Combination 
{
     List<List<int>> combination;

     public override bool Equals(Object obj) {...};

     public Combination operator* (Combination c1, Combination c2) {...};

     public Combination operator+ (Combination c1, Combination c2) {...};
}

请注意，等式 (1) 中包含重复组合 C2 和 C3，为了加快程序速度，我们可以使用哈希集来保存所有计算出的组合（如封闭列表）：

HashSet<Combination> calculatedCombinations = new HashSet<Combination>(){};

现在我们应该做另一个技巧，注意：

C2 = {{1, 1}, {2}}   (3)

但它可以写成：

C2 = {{2}, {1, 1}}   (4)

所以当我们重写Equals()的时候，必须要处理(3)和(4)，我的意见是把C2转换成一个扁平有序的数组，创建一个辅助函数：

private int[] convertCombination(Combination c) {...};

然后 convertCombination(C2) = {1, 1, 2} 这是一个统一的形式，所以内部 Equals() 可以使用这个函数来存储对象。希望这对你有帮助。

Att：如果输入列表的数字大于目标数字，则在遍历列表时应忽略此数字。

推荐阅读