|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.11.2011, 18:58 | #1 |
Пользователь
Регистрация: 08.11.2007
Сообщений: 91
|
Олимпиадная задача
Имеется N предметов, веса которых соответственно равны a1, a2, ... an. Разделить эти предметы на 2 группы так, чтобы общие веса групп были максимально близки.
Не могу решить эту задачу. Не знаю даже с чего начать. Была идея раскидывать грузы по очереди, то есть каждый раз смотреть в какой группе меньше сумма грузов, туда груз и добавлять, но это не правильно. Пример грузов: 25, 16, 9, 36, 41. Правильный ответ: 1я группа - 25+41=66. 2я группа - 16+9+36=61. При сортировке что по возрастанию, что по убыванию правильного ответа не получается.
Не мы такие, жизнь такая...
|
09.11.2011, 19:12 | #2 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Тут нет алгоритма кроме перебора.
|
09.11.2011, 19:41 | #3 |
Форумчанин
Регистрация: 31.05.2010
Сообщений: 407
|
а что если так
1 определяем средний вес (25+ 16+ 9+ 36+ 41)/2=63,5 2 полный перебор: --- сумма до первого превышения ср веса ------сумма оствышихся --------если разность меньше предыдущей --- запомнить наборы
icq 584 308 611
|
09.11.2011, 19:45 | #4 |
Software Developer
Участник клуба
Регистрация: 01.03.2011
Сообщений: 1,098
|
Уже обсуждалась эта задача тут.
Поищи...
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062 |
09.11.2011, 23:03 | #5 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
почитайте тему по ссылке ниже.. Цитата:
я поискал. вот она - Разделение предметов по весу пост #2 (c) Smitt&Wesson в данной теме даёт нужный алгоритм. p.s. алгоритм крайне простой и эффективный. Единственный недостаток - он не всегда даёт оптимальное решение. Зато он всегда даёт решение чтобы "общие веса групп были максимально близки" |
||
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Олимпиадная задача | Saidoz | Паскаль, Turbo Pascal, PascalABC.NET | 7 | 28.10.2011 13:02 |
Олимпиадная задача. | masashama | Общие вопросы C/C++ | 19 | 27.10.2011 14:52 |
олимпиадная задача | danzel1 | Общие вопросы C/C++ | 2 | 21.10.2011 15:15 |
Олимпиадная задача | Alexey_kor | Помощь студентам | 7 | 30.01.2011 02:22 |
Олимпиадная задача | Carbon | Общие вопросы C/C++ | 2 | 23.05.2007 22:07 |