Kd
есть список из чисел, и надо проверить возможно ли из этого списка взять числа, сумма которых будет равна n
проверить что в заданом множестве чисел есть такое подмножество, что сумма всех его членов равна заданой сумме n
Size: a a a
2021 January 31
с#
Konstantin dmz9
проверить что в заданом множестве чисел есть такое подмножество, что сумма всех его членов равна заданой сумме n
+
YN
есть список из чисел, и надо проверить возможно ли из этого списка взять числа, сумма которых будет равна n
Надеюсь, по одному разу можно брать эти числа?
YN
Konstantin dmz9
общий случай это доказательство что сумма (a(n)) == x
но если рекурсивно то это a (n-1) = x - a(n)
но если рекурсивно то это a (n-1) = x - a(n)
Я думаю, рекурсивно эта задача не решается.
Думаю, надо решать её просто перебором.
Рассмотреть все возможные суммы всех чисел из x (с понятной оптимизацией остановки при нахождении), если n среди них, то ответ да.
Думаю, надо решать её просто перебором.
Рассмотреть все возможные суммы всех чисел из x (с понятной оптимизацией остановки при нахождении), если n среди них, то ответ да.
d
есть список из чисел, и надо проверить возможно ли из этого списка взять числа, сумма которых будет равна n
Ну вот, теперь можно говорить о задаче. Задаче о сумме подмножеств
Kd
Я думаю, рекурсивно эта задача не решается.
Думаю, надо решать её просто перебором.
Рассмотреть все возможные суммы всех чисел из x (с понятной оптимизацией остановки при нахождении), если n среди них, то ответ да.
Думаю, надо решать её просто перебором.
Рассмотреть все возможные суммы всех чисел из x (с понятной оптимизацией остановки при нахождении), если n среди них, то ответ да.
решается. из множества надо сделать сортированую последовательность. дальше, отсекая от суммы и последовательности по одному элементу доказывать можем ли мы для остатков доказать то же самое
Kd
ну или можно не оптимизировать, не сортироватт заранее
с#
Konstantin dmz9
ну или можно не оптимизировать, не сортироватт заранее
они сортированные если что
с#
ну по возрастанию
с#
хотя появилась идея, сейчас попробую
Kd
можно ли из чисел 1 2 3 4 5 сделать сумму 12, это рекурсивно означает найти доказательства что, например, для множества 1 2 3 4 можно найти сумму 7
d
хотя появилась идея, сейчас попробую
Зумер, хватит пробовать. Задача о сумме подмножеств/задача о рюкзаке
Kd
если найти рекурсивно варианты с этим отброшеным элементом нельзя значит пытаемся искать сумму без него, т.е. последоваткльность уменьшается
YN
Konstantin dmz9
если найти рекурсивно варианты с этим отброшеным элементом нельзя значит пытаемся искать сумму без него, т.е. последоваткльность уменьшается
Но это просто перебор.
Kd
Но это просто перебор.
рекурсия с перебором.
можно только перебор - это суммирование по порядку всех перестановок
можно только перебор - это суммирование по порядку всех перестановок
YN
Konstantin dmz9
рекурсия с перебором.
можно только перебор - это суммирование по порядку всех перестановок
можно только перебор - это суммирование по порядку всех перестановок
Число всех комбинаций в списке из k элементов есть 2^k.
Ваша рекурсия - просто реализация перебора, но вычислительно ничего не меняется.
Ваша рекурсия - просто реализация перебора, но вычислительно ничего не меняется.
d
Пиздец пропаганда в глаза ссыт - и чаем угощают и колеса сменить помогают и через улицу переводят и маски предлагают....
d
надеюсь с лимоном, а не полонием
AD
Пиздец пропаганда в глаза ссыт - и чаем угощают и колеса сменить помогают и через улицу переводят и маски предлагают....
мой любимый канал по теме, велкам
https://t.me/mig41/7573
https://t.me/mig41/7573
