 |
|
Модераторы: Daevaorn |
 
|
|
Олимпиадная задача 
| Lacoste1024 |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 69 Регистрация: 20.3.2011 Репутация: нет Всего: 1 |
Имеется N предметов, веса которых соответственно равны a1, a2, ... an. Разделить эти предметы на 2 группы так, чтобы общие веса групп были максимально близки.
Не могу решить эту задачу. Не знаю даже с чего начать. Была идея раскидывать грузы по очереди, то есть каждый раз смотреть в какой группе меньше сумма грузов, туда груз и добавлять, но это не правильно. Это сообщение отредактировал(а) Lacoste1024 - 9.11.2011, 17:02 |
|||
|
||||
Загрузка ...
| bsa |
|
|||
 Эксперт Профиль Группа: Модератор Сообщений: 9185 Регистрация: 6.4.2006 Где: Москва, Россия Репутация: 63 Всего: 196 |
отсортируй в порядке убывания веса. затем бери очередной груз и добавляй его в ту группу, которая содержит наименьший вес.
|
|||
|
||||
| Lacoste1024 |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 69 Регистрация: 20.3.2011 Репутация: нет Всего: 1 |
Этот вариант я тоже пробовал. Не подходит. Пример грузов: 25, 16, 9, 36, 41. Правильный ответ: 1я группа - 25+41=66. 2я группа - 16+9+36=61. При сортировке что по возрастанию, что по убыванию правильного ответа не получается. |
|||
|
||||
| math64 |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 2505 Регистрация: 12.4.2007 Репутация: 8 Всего: 72 |
Отсортировать по весам - правильное действие.
Далее, определить общий вес и поделить пополам. Дальше нужно стремиться получить набор предметов весом менльше половины, как можно ближе к ней. Второй набор определиться автоматически. Если число предметов не превышает 32(64), набор опреляется числом uint32(uint64), в котором i-й бит устанавливается в 1 если i-й предмет включен в набор. Если предметов больше, нужно использовать bitset. |
|||
|
||||
| Silent |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 252 Регистрация: 3.10.2006 Репутация: нет Всего: 9 |
Обычная динамика.
Считаешь общий вес, находишь половину - это "идеальный вес", который должен быть. А дальше - классическая задача о камнях, нужно набрать не больше "идеального веса". Литература - Окулов, Программирование в алгоритмах, страница 101-102 |
|||
|
||||
| lamber |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 143 Регистрация: 20.12.2008 Репутация: нет Всего: нет |
способ предложенный math64 является правильным, остальные мульки с сортировками не верны, задача на полный перебор (если я не пру, то это как раз тот тип задач над решением, которых и стоит вопрос P!=NP или P==NP входит в одну из 10-ти задач тысячелетия, могу буровить если что знатоки поправьте ). Если ответ не получен могу скинуть исходник для решения подобных задач.
|
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0729 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |