Поиск всех возможных комбинаций чисел для достижения заданной суммы
Как бы вы протестировали все возможные комбинации дополнений из заданного набора N чисел, чтобы они суммировались с заданным окончательным числом?
- Набор номеров для добавления: N =
- Желаемый результат: 12345
Эта проблема может быть решена с помощью рекурсивных комбинаций всех возможных сумм, отфильтровывающих те, которые достигают цели. Вот алгоритм в Python:
Этот тип алгоритмов очень хорошо объяснен в следующей лекции Standford по абстрактному программированию — это видео очень рекомендуется, чтобы понять, как работает рекурсия для генерации перестановок решений.
редактировать
Выше, как функция генератора, что делает его немного более полезным. Требуется Python 3.3+ из-за yield from .
Вот Java-версия того же алгоритма:
Это точно такая же эвристика. Моя Java немного ржавая, но я думаю, что это легко понять.
C # преобразование решения Java: (@JeremyThompson)
Решение Ruby: (@emaillenin)
Редактировать: обсуждение сложности
Как уже упоминали другие, это NP-сложная проблема . Его можно решить за экспоненциальное время O (2 ^ n), например, при n = 10 будет 1024 возможных решения. Если цели, которые вы пытаетесь достичь, находятся в низком диапазоне, то этот алгоритм работает. Так, например:
subset_sum([1,2,3,4,5,6,7,8,9,10],100000) генерирует 1024 ветви, потому что цель никогда не получает возможность отфильтровать возможные решения.
С другой стороны, subset_sum([1,2,3,4,5,6,7,8,9,10],10) генерирует только 175 ветвей, потому что цель, которую нужно достичь, 10 отфильтровывает множество комбинаций.
Если N и Target большие числа, следует перейти к приблизительному варианту решения.
Решение этой проблемы было дано миллион раз в Интернете. Проблема называется проблемой смены монет . Решения можно найти по адресу http://rosettacode.org/wiki/Count_the_coins и его математическую модель по адресу http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (или обмен монет Google проблема ).
Кстати, решение Scala от Tsagadai, интересно. В этом примере выводится либо 1, либо 0. В качестве побочного эффекта на консоли выводятся все возможные решения. Он отображает решение, но не делает его пригодным для использования каким-либо образом.
Чтобы быть как можно более полезным, код должен возвращать a List[List[Int]] , чтобы можно было получить номер решения (длина списка списков), «лучшее» решение (самый короткий список) или все возможные решения.
Вот пример. Это очень неэффективно, но это легко понять.
При запуске он отображает:
sumCombinations() Функция может быть использована сама по себе, и результат может быть дополнительно проанализированы , чтобы отобразить «лучший» решение (самый короткий список), или число решений (количество списков).
Обратите внимание, что даже в этом случае требования могут быть не полностью выполнены. Может случиться так, что порядок каждого списка в решении будет значительным. В таком случае каждый список должен дублироваться столько раз, сколько существует комбинация его элементов. Или нас могут интересовать только разные комбинации.
Например, мы могли бы рассмотреть, что List(5, 10) должно дать две комбинации: List(5, 10) и List(10, 5) . За List(5, 5, 5) это можно дать три комбинации или только одну, в зависимости от требований. Для целых чисел три перестановки эквивалентны, но если мы имеем дело с монетами, как в «проблеме смены монет», то это не так.
В требованиях также не указан вопрос о том, можно ли использовать каждый номер (или монету) только один или несколько раз. Мы могли бы (и мы должны!) Обобщить проблему в список списков вхождений каждого числа. В реальной жизни это переводится как «как можно заработать определенную сумму денег с помощью набора монет (а не набора ценностей монет)». Первоначальная проблема — это только частный случай этой проблемы, когда у нас есть столько экземпляров каждой монеты, сколько необходимо, чтобы составить общую сумму для каждой отдельной стоимости монеты.
Задачи по C++. Максимальное число из трех
Условие задачи : Определить какое из трех, введенных пользователем чисел максимальное и вывести его на экран.
Сложность : легкая.
Для того чтобы решить эту задачу, мы будем делать следующее :
Мы возьмем первые два числа и для начала сравним их и которое больше мы присвоим значение максимального.
Затем мы будем сравнивать последнее число с текущим максимальным.
Тут мы просто объявили 4 переменные. Дальше попросим пользователя ввести 3 числа и напишем первое условие:
Тут всё просто. После того как мы ввели три числа мы начинаем сравнивать первые два числа и в переменную max заносим большее из них.
Теперь у нас есть наибольшее число. Но нам надо еще сравнить его еще с переменной num3, если num3 окажется больше текущей переменной max, то мы присвоим переменной max значение num3:
Нахождение суммы комбинаций чисел для целого числа с использованием трех чисел
Для заданного целого числа, n, мне нужно напечатать все списки длины 3 которые сумируются до n. Члены списка должны быть неотрицательными целыми числами. После печати всех этих списков, он должен затем напечатать количество списков которые были найдены.
Например если n=2:
- 1+0+1 = 2
- 1+1+0 = 2
- 0+1 = 2
- 2+0 = 2
- 0+2 = 2
- 0+2+0 = 2
Вот такую программу я сделал для списков длины 2 а не списков длины 3:
Цель состоит в том чтобы расширить данный со списков длины два на списки длины 3.
Дополнительная инфа: Я могу использовать только одну другую переменную c3.
4 ответа
Надежда вот это поможет:
Если вас интересует только число ответ — это комбинация с повторением total + 1 элементов 2-го класса: Давайте я поясню так: Пусть мы считаем total числом из 1s. У них есть total + 1 промежутки между подсчетом промежутка перед первым 1 и после последнего. Вы пытаетесь выбрать 3 числа, которые суммируют до total: сделаем, что бы расставив до разделителей в промежутках я только что объяснил. Первое число будет суммой единиц перед первыми разделителями, второе — количеством единиц между разделителями, третье — оставшимися. Обратите внимание, что т.к мы позволяем числам быть нулевым мы позволяем разделителям помещаться в тот же промежуток и так же быть перед первым 1 и после последнего 1. Это точно эквивалентно «комбинации с повторением total + 1 элементов 2-го класса» как я уже сказал и является классической комбинаторной проблемой. Можете почитать про те самые комбинации here но в основном ответ будет ((total + 1) * (total + 2)) / 2. Btw я бы предложил перетачить эту проблему хотя бы тегом algorithm.
EDIT: следуя просьбе дальнейшего объяснения, я просто проиллюстрирую все свои мысли примером (собственно на том же примере, который вы дали в вопросе): нам нужно разбить 2 на три группы. 2 приводит нас к количеству одних мы должны написать: _1_1_. Вот у меня написаны так называемые-by-me пробелы с ‘_’. Теперь, обозначим два разделителя с ‘|’. Опять разделители используются для определения того, какая сумма 1ов используется для первого, второго и третьего числа в разбиении sum. Слева я пишу комбинацию используя свою нотацию а справа соответствующее сочетание в вашей нотации.
Теперь, надеюсь, вы лучше понимаете что такое разделители и как они используются для определения того, что такое три числа, используемые в комбинации. Если вы увеличите total логика остается та же, но нужно будет писать больше, если вам нужно будет проиллюстрировать случай.
Наверное, теперь вы тоже понимаете, почему пробелы именно total + 1 и как может случиться, что каждый из двух разделителей находится в каждом из этих двух пробелов. Все это приводит нас к обещанной комбинации с повторением total + 1 элементов 2-го класса.