Алгоритм, чтобы найти, какие числа из списка размером n сумма к другому числу

Question

У меня есть десятичное число (назовем его цель ) и массив других десятичных чисел (назовем массив elements ), и мне нужно найти все комбинации чисел от элементов , которые суммируются с целью.

У меня есть предпочтение для решения на C # (.Net 2.0), но, возможно, лучший алгоритм победит независимо от этого.

Ваша подпись метода может выглядеть примерно так:

public decimal[][] Solve(decimal goal, decimal[] elements)

Answer 1

Интересные ответы. Спасибо за указатели на Википедию, хотя они и интересны, но на самом деле они не решают проблему, как я уже говорил, поскольку я искал точные совпадения, - скорее проблема учета / балансировки книг, чем традиционная проблема упаковки / ранцев.

Я с интересом следил за развитием переполнения стека и удивлялся, насколько это будет полезно. Эта проблема возникла на работе, и я подумал, может ли переполнение стека дать готовый ответ (или лучший ответ) быстрее, чем я мог бы написать его сам. Спасибо также за комментарии, предлагающие пометить это домашнее задание - я думаю, что это достаточно точно в свете вышесказанного.

Для тех, кто заинтересован, вот мое решение, которое использует рекурсию (естественно). Я также передумал насчет сигнатуры метода и выбрал List>, а не decimal [] [] в качестве возвращаемого типа:

public class Solver {

    private List<List<decimal>> mResults;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {

        mResults = new List<List<decimal>>();
        RecursiveSolve(goal, 0.0m, 
            new List<decimal>(), new List<decimal>(elements), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, 
        List<decimal> included, List<decimal> notIncluded, int startIndex) {

        for (int index = startIndex; index < notIncluded.Count; index++) {

            decimal nextValue = notIncluded[index];
            if (currentSum + nextValue == goal) {
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
            }
            else if (currentSum + nextValue < goal) {
                List<decimal> nextIncluded = new List<decimal>(included);
                nextIncluded.Add(nextValue);
                List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
                nextNotIncluded.Remove(nextValue);
                RecursiveSolve(goal, currentSum + nextValue,
                    nextIncluded, nextNotIncluded, startIndex++);
            }
        }
    }
}

Если вы хотите, чтобы приложение протестировало это, попробуйте этот код консольного приложения:

class Program {
    static void Main(string[] args) {

        string input;
        decimal goal;
        decimal element;

        do {
            Console.WriteLine("Please enter the goal:");
            input = Console.ReadLine();
        }
        while (!decimal.TryParse(input, out goal));

        Console.WriteLine("Please enter the elements (separated by spaces)");
        input = Console.ReadLine();
        string[] elementsText = input.Split(' ');
        List<decimal> elementsList = new List<decimal>();
        foreach (string elementText in elementsText) {
            if (decimal.TryParse(elementText, out element)) {
                elementsList.Add(element);
            }
        }

        Solver solver = new Solver();
        List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
        foreach(List<decimal> result in results) {
            foreach (decimal value in result) {
                Console.Write("{0}\t", value);
            }
            Console.WriteLine();
        }


        Console.ReadLine();
    }
}

Надеюсь, это поможет кому-то еще быстрее получить ответ (будь то домашнее задание или иное).

Приветствия ...

Answer 2

Проблема сумм подмножеств и чуть более общая проблема ранцев решаются с помощью динамического программирования: перечисление всех комбинаций методом грубой силы не требуется. Проконсультируйтесь с Википедией или вашими любимыми ссылками на алгоритмы.

Хотя задачи являются NP-полными, они очень «легки» для NP-полноты. Алгоритмическая сложность по количеству элементов мала.

Answer 3

Я думаю, что у вас есть проблема с упаковкой бин в ваших руках (которая NP-сложная), поэтому я думаю, что единственное решение будет в том, чтобы попробовать каждую возможную комбинацию, пока вы не найдете ту, которая работы.

Редактировать: Как указано в комментарии, вам не нужно всегда пытаться каждую комбинацию для каждого набора чисел, с которым вы столкнетесь. Однако любой метод, который вы придумали, имеет наборы чисел в наихудшем сценарии, где вам придется попробовать каждую комбинацию - или, по крайней мере, подмножество комбинаций, которое растет экспоненциально с размер набора.

В противном случае, это не будет NP-сложным.

Answer 4

Несмотря на то, что проблема грубой силы не решается (как уже упоминалось), вы можете сначала отсортировать свои числа, а затем перейти к оставшимся возможным (поскольку после того, как вы передали значение Sum, вы не можете добавить любое большее число). чем гол - сумма).

Это изменит способ реализации вашего алгоритма (чтобы отсортировать только один раз, а затем пропустить отмеченные элементы), но в среднем повысит производительность.

Answer 5

Вы описали проблему ранца , единственное верное решение - грубая сила. Существует несколько приближенных решений, которые работают быстрее, но могут не соответствовать вашим потребностям.

Answer 6

public class Logic1 {
    static int val = 121;
    public static void main(String[] args)
    {
        f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{");
    }

    static void f(int[] numbers, int index, int sum, String output)
    {
        System.out.println(output + " } = " + sum);
        //System.out.println("Index value1 is "+index);
        check (sum);
        if (index == numbers.length)
        {
            System.out.println(output + " } = " + sum);
            return;
        }

        // include numbers[index]
        f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
        check (sum);
        //System.out.println("Index value2 is "+index);
        // exclude numbers[index]
        f(numbers, index + 1, sum, output);
        check (sum);
    }

    static void check (int sum1)
    {
        if (sum1 == val)
            System.exit(0);
    }
}