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

Question

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

例如如果目标是 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;
    }

Answer 1

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

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

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

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() 内部可以使用这个函数来比较对象。希望对您有所帮助。

注意:如果输入列表中有一个数字大于目标数字，那么在遍历列表时应该忽略这个数字。