| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Разделить ряд чисел на два с равными суммами |
| Автор: MichaelMPEI 7.2.2006, 23:30 |
| Дан ряд случайных чисел. Необходимо его разделить на 2 так, чтобы сумма чисел в каждом из них была одинакова. Простым перебором слишком долго. Может, кто подскажет метод побыстрее? Заранее спасибо. |
| Автор: knark 7.2.2006, 23:53 |
| Сумма чисел где? |
| Автор: MichaelMPEI 8.2.2006, 01:42 |
| Сумма чисел в каждом из полученных рядов. Например есть ряд: 1, 2, 3, 4, 6, 7, 8, 9. Первый ряд: 1, 2, 8, 9. Сумма 20 Второй ряд: 3, 4, 6, 7. Сумма 20 |
| Автор: sergejzr 8.2.2006, 02:23 | ||
| исходя из условия у нас есть две суммы А и Б и что что А=Б=общая_сумма/2 То есть Задача сводится к нахождению группы чисел, которая в сумме даст А. Придётся таки все перебирать на это условие. Это вроде один из подразделов "магического" квадрата. Там тоже только перебор. Но это лучше, чем перебирать по начальному условию. Ограничения, если числа сгенерены случайно. Решение отсутствует, если: Общая сумма всех чисел не кратна 2. Все числа позитивны и присутсвует число Х, и Х > А -> Разделить будет невозможно. Добавлено @ 02:27
В йтом примере будет работатьтак: summa= 1+2+3+4+6+7+8+9; //=40; A=summa/2; //=20 Осталось найти, какие числа из 1, 2, 3, 4, 6, 7, 8, 9 в сумме дадут 20 |
| Автор: cardinal 8.2.2006, 02:45 |
| А если A число нечетное, то можно подумать над тем не лепить ли его из нечетных чисел сначала, а лишь потом если не получится работать с четными. Ну и если А четное, то соответственно наоброт. В данном случае А = 20 значит идем и складываем все четные числа 2+4+6+8... о 20  значит больше ничего делать не надо. |
| Автор: sergejzr 8.2.2006, 02:52 |
| только вопрос, возможны ли там негативные числа также и/или одинаковые |
| Автор: SoWa 8.2.2006, 05:58 | ||
| Я считаю что все просто: Сортируешь ряд исходных чисел, потом первое и последнее счисло в ряд1, второе и предпоследнее в ряд2, третье и ... в ряд1 ит.д. Потом уже перебором корректируешь эти ряды. Для ряда 1 2 3 4 5 6 7 8 9 будет так: ряд1: 1 9 3 7 ряд2: 2 8 4 6 Корректировки в данном случае не нужны. В другом случае могут быть. Добавлено @ 05:59
Да. Если это так, то корректировки делать бесполезно. |
| Автор: Akina 8.2.2006, 10:09 |
| Ну блин же ж... задача о рюкзаке в чистейшем виде... чего спрашивать-то? |
| Автор: SoWa 8.2.2006, 20:02 | ||
Это что такое? И как решать тогда? |
| Автор: esperant0 8.2.2006, 23:07 |
| только перебор это классическая НП полная задача |
| Автор: Akina 9.2.2006, 10:14 | ||||
Поиск никто не отменял. В т.ч. в Инете.
NP-полная задача с временем O(n)??? ну-ну.. |
| Автор: esperant0 9.2.2006, 16:18 | ||||||
http://www.cs.brown.edu/courses/cs051/assign/hw10.sol.ps Посмотрите тут вторую задачу. Она НП полная, но в то жевремя немного проще задачи, решенной вами за линейное время. Видимо вы доказали что НП=П. Поздравляю. с уважением |
