Столкнулся с такой проблемой: Дан массив целых чисел (не больше 50 елементов). Надо сказать, не является ли любое из чисел суммой нескольких других из этого массива. Не знаю как это сделать эфективно.
Столкнулся с такой проблемой: Дан массив целых чисел (не больше 50 елементов). Надо сказать, не является ли любое из чисел суммой нескольких других из этого массива. Не знаю как это сделать эфективно.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 164 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Не знаю как это сделать эфективно.http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1007&rid=50e34132eff8a
На таких ограничениях рюкзак проще всего, а если бы числа были произвольными, meet-in-the-middle можно применять.
Можно по-подробнее с meet-in-the-middle?
Делим элементы на две равные части, генерируем в каждой из частей суммы всех подмножеств. Все суммы вместе с соответствующими битмасками сохраняем в два массива, по одному для каждой части. После этого перебираем все элементы и идем двумя указателями по массивам, пытаясь набрать нужную сумму. При этом в том массиве, откуда родом рассматриваемый элемент, не надо учитывать те подмножества, куда он входит. O(n·20.5n) должно зайти.
И да, я считаю, что для зеленых как рюкзак, так и meet-in-the-middle слишком сложно, лучше сначала научиться безошибочно решать халяву и приобрести олимпиадное мышление. Это гарантированно принесет фиолетовый цвет, и только потом уже можно начинать изучать алгоритмы с пользой для себя. Вот так.
Рюкзак не смог написать(решение пытается минимальным путем дойти). Вот рекурсия (не знаю пройдет ли по времени).
UPD: В решении с рекурсии размер массива
aлучше увеличить до 110.При небольших ограничениях можно сложить рюкзак, параллельно считая количество чисел в каждом элементе рюкзака. Потом пройти по рюкзаку, смотря только на те элементы, которые составлены более, чем из 1 числа, и проверять, есть ли число в последовательности, равное элементу рюкзака. Соответственно проставлять в последовательности true. Потом проверить, все ли числа из последовательности помечены, как true. Вот тут читать про рюкзак.