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

Question

Что такое нерекурсивный алгоритм для определения того, может ли переданная сумма быть построена аддитивно из набора чисел.
В моем случае я определяю, может ли быть достигнута определенная сумма в валюте (например, 40 долларов), складывая некоторую комбинацию из набора счетов (например, 5, 10 и 20 долларов). Это простой пример, но алгоритм должен работать для любого набора валют (в некоторых валютах используются суммы счетов в стиле фанк, а некоторые счета могут быть недоступны в данный момент времени).
Таким образом, $ 50 можно встретить с набором ($ 20 и $ 30), но нельзя встретить с набором ($ 20 и $ 40). Нерекурсивное требование обусловлено тем, что целевая база кода составляет SQL Server 2000, где поддержка рекурсии ограничена.
Кроме того, это делается для поддержки мультивалютной среды, в которой может изменяться набор доступных счетов (например, кассир по обмену иностранной валюты).

Answer 1

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

Максимальное количество нот, которое вам понадобится, равно сумме, которая вам требуется, деленной на банкноту с наименьшим номиналом.

Это грубая реакция на проблему, но она определенно сработает.

Вот немного p-кода. Я, наверное, повсюду со своими столбами забора, и это настолько неоптимизировано, чтобы быть смешным, но это должно работать. Я думаю, идея в любом случае верна.

Denominations = [10,20,50,100]
Required = 570

Denominations = sort(Denominations)
iBase = integer (Required / Denominations[1])

BumpList = array [Denominations.count]
BumpList.Clear

repeat 
    iTotal = 0 
    for iAdd = 1 to Bumplist.size
        iTotal = iTotal + bumplist [iAdd] * Denominations[iAdd]
    loop
    if iTotal = Required then exit true

    //this bit should be like a mileometer. 
    //We add 1 to each wheel, and trip over to the next wheel when it gets to iBase
    finished = true
    for iPos from bumplist.last to bumplist.first 
        if bumplist[iPos] = (iBase-1) then bumplist[iPos] = 0 
        else begin
            finished = false
            bumplist[iPos] = bumplist[iPos]+1
            exit for
        end
     loop 
until (finished)

exit false    

Answer 2

Вы уже дважды заявляли, что алгоритм не может быть рекурсивным, но это естественное решение этой проблемы. Так или иначе, вам нужно будет выполнить поиск, чтобы решить эту проблему. Если рекурсия отключена, вам придется вернуться назад вручную.

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

По сути, это рекурсивное решение в цикле с управляемым вручную стеком.

Answer 3

Это звучит как проблема суммы подмножеств, которая, как известно, является NP-полной .

Удачи с этим.

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

Answer 4

Эту проблему можно решить с помощью подхода, известного как динамическое программирование. К сожалению, мои лекционные заметки слишком сфокусированы на биоинформатике, поэтому вам придется поискать их самостоятельно.

Answer 5

Вы можете решить эту проблему с помощью метода Динамическое программирование в качестве MattW. упоминается.

Учитывая ограниченное количество счетов и максимальную сумму денег, вы можете попробовать следующее решение. Фрагмент кода на C #, но я считаю, что вы можете легко перенести его на другой язык.

        // Set of bills
        int[] unit = { 40,20,70};

        // Max amount of money
        int max = 100000;

        bool[] bucket = new bool[max];

        foreach (int t in unit)
            bucket[t] = true;

        for (int i = 0; i < bucket.Length; i++)
            if (bucket[i])
                foreach (int t in unit)
                    if(i + t < bucket.Length)
                        bucket[i + t] = true;

        // Check if the following amount of money
        // can be built additively
        Console.WriteLine("15 : " + bucket[15]);
        Console.WriteLine("50 : " + bucket[50]);
        Console.WriteLine("60 : " + bucket[60]);
        Console.WriteLine("110 : " + bucket[110]);
        Console.WriteLine("120 : " + bucket[120]);
        Console.WriteLine("150 : " + bucket[150]);
        Console.WriteLine("151 : " + bucket[151]);

Выход:

15 : False
50 : False
60 : True
110 : True
120 : True
150 : True
151 : False

Answer 6

Я согласен с Тайлером - то, что вы описываете, является вариантом проблемы Subset Sum , которая известна как NP-Complete . В этом случае вам немного повезло, поскольку вы работаете с ограниченным набором значений, поэтому вы можете использовать здесь методы динамического программирования , чтобы немного оптимизировать проблему. С точки зрения некоторых общих идей для кода:

• Поскольку вы имеете дело с деньгами, существует только так много способов внести изменения в данный счет, и в большинстве случаев некоторые счета используются чаще, чем другие. Таким образом, если вы сохраняете результаты, вы можете сохранить набор наиболее распространенных решений, а затем просто проверить их, прежде чем пытаться найти реальное решение.
• Если язык, с которым вы работаете, не поддерживает рекурсию, нет никаких оснований полностью игнорировать использование рекурсии в решении. Хотя любую рекурсивную проблему можно решить с помощью итерации, в этом случае рекурсию, вероятно, будет легче написать.

Некоторые другие пользователи, такие как Kyle и seanyboy , указывают вам правильное направление для написания собственной функции, поэтому вам следует взглянуть на то, что они предоставили для того, что работаем над.

Answer 7

Алгоритм: 1. Сортировать валютные купюры по убыванию.
2. Рассчитать остаток = Ввод% номинала [i] i -> n-1, 0
3. Если остаток равен 0, вход может быть разбит, иначе не может быть.

Пример:
Вход: 50, доступно: 10,20
[50% 20] = 10, [10% 10] = 0, Ответ: Да Вход: 50, доступно: 15,20
[50% 20] = 10, [10% 15] = 15, ответ: нет

Answer 8

Существует разница между отсутствием рекурсии и ограниченной рекурсией. Не путайте их, потому что вы пропустили смысл урока.

Например, вы можете безопасно написать факториальную функцию, используя рекурсию на C ++ или других языках низкого уровня, потому что ваши результаты переполнят даже ваши самые большие контейнеры в пределах нескольких рекурсий. Таким образом, проблема, с которой вы столкнетесь, заключается в сохранении результата до того, как он когда-либо взорвется вашим стеком из-за рекурсии.

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

Вам не нужно вообще избегать рекурсии, если ваша платформа поддерживает наихудший сценарий.

Answer 9

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

Постройте его, начиная с самого большого счета в сторону самого маленького. Это даст наименьшее количество счетов.

Возьмите начальную сумму и внесите наибольший счет столько раз, сколько сможете, не превышая цену.

Перейдите к следующему по величине счету и примените его таким же образом.

Продолжайте делать это, пока не получите самый маленький счет.

Затем проверьте, равна ли сумма целевому значению.