Как найти все комбинации выбора данной суммы?
Дана сумма, например 25, и даны числа, например 2, 5, 10
Нужно найти все комбинации выбора данной суммы.
То есть программа должна вывести 5 + 5 + 5 + 5 + 5, 5 + 5 + 5 + 10, 5 + 10 + 10, 2 + 2 + 2 + 2 + 2 + 10 + 5 и тд.
Какими алгоритмами / методами / библиотеками посоветуете воспользоваться?
Ответы (2 шт):
Автор решения: aleksandr barakin
→ Ссылка
требуется алгоритм? возьмите за основу что-нибудь типа этого:
функция поиск (сумма, допустимые_слагаемые, список_слагаемых) {
если сумма = 0, то {
напечатать список_слагаемых
возврат
}
если допустимые_слагаемые = пусто, то возврат
слагаемое := первый_элемент_списка (допустимые_слагаемые)
допустимые_слагаемые := убрать_первый_элемент_списка (допустимые_слагаемые)
для количество_слагаемых от 0 до сумма / слагаемое {
вызов функции поиск (сумма, допустимые_слагаемые, список_слагаемых)
сумма := сумма - слагаемое
если сумма < 0 то возврат
список_слагаемых := добавить_элемент_в_список (список_слагаемых, слагаемое)
}
}
исходная_сумма := 25
допустимые_слагаемые := 2 5 10
текущий_список_слагаемых := пусто
вызов функции поиск (исходная_сумма, допустимые_слагаемые, текущий_список_слагаемых)
Автор решения: Аркадий
→ Ссылка
Почитай задачи о рюкзаковании, вот подробная статья, например https://informatics.msk.ru/mod/book/view.php?id=815&chapterid=60