|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.04.2012, 13:30 | #1 |
Пользователь
Регистрация: 22.02.2012
Сообщений: 15
|
(Классика) Куча камней сортировка НЕ пузырьком.
У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.
Исходные данные Ввод содержит количество камней N (1 ≤ N ≤ 20) и веса камней W1, …, Wn (1 ≤ Wi ≤ 100 000) — целые, разделённые пробельными символами. Результат Ваша программа должна вывести одно число — минимальную разность весов двух куч. Код:
6 1 4 5 6 7 9 0 А у меня 6 1 4 5 6 7 9 2 -2 Скажите какой сортировкой воспользоваться ? |
28.04.2012, 14:22 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
то, что Вы отстортировали по весу - это правильно.
а вот потом, Вы, вероятно, неправильно распределяете элементы по весу. рекомендую почитать вот эту тему: Разделение предметов по весу и взять предложенный в ней алгоритм (пост #2 (c) Smitt&Wesson а, учтите, что полученное решение будет близким к оптимальному, НО, разумеется, НЕ ОПТИМАЛЬНЫМ (я там в теме об этом говорил). если нужно оптимальное решение - то нужен перебор всех вариантов, конечно! Добавлено посмотрел на ваш пример. нет, упрощённый алгоритм вам не подойдёт. нужен перебор! о переборе (и коды) можете почитать в темах Жадный алгоритм и перебор Выборка чисел особенно обратите внимание на посты от (c) LeBron - судя по всему, это Гуру олимпиад по программированию! Последний раз редактировалось Serge_Bliznykov; 28.04.2012 в 14:51. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
сортировка пузырьком | onezze | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 09.04.2012 16:18 |
Задача - куча камней. | InKo1 | Общие вопросы C/C++ | 11 | 04.01.2012 18:23 |
Сортировка пузырьком с++ | FroLe | Общие вопросы C/C++ | 6 | 20.12.2010 01:23 |
Сортировка пузырьком | Авторитет | Общие вопросы .NET | 4 | 15.11.2010 19:50 |