Как получить все комбинации набора чисел, которые будут складываться или только немного превышать установленный номер?

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 отправила мне «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: Если у входного списка есть номер, который больше целевого числа, то этот номер следует игнорировать при обходе списка.

Answer 2

Вы можете использовать динамическое программирование для решения проблем, которые выглядят таким образом, это зависит от того, как пробовать все (все возможные способы) ответов, но с ограничением, чтобы избежать превышения лимита времени.В этой задаче вы можете использовать DP (Динамическое программирование) 2D.Вы можете увидеть Динамическое программирование !