| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Олимпиадная задача |
| Автор: Lacoste1024 9.11.2011, 17:00 |
| Имеется N предметов, веса которых соответственно равны a1, a2, ... an. Разделить эти предметы на 2 группы так, чтобы общие веса групп были максимально близки. Не могу решить эту задачу. Не знаю даже с чего начать. Была идея раскидывать грузы по очереди, то есть каждый раз смотреть в какой группе меньше сумма грузов, туда груз и добавлять, но это не правильно. |
| Автор: bsa 9.11.2011, 17:16 |
| отсортируй в порядке убывания веса. затем бери очередной груз и добавляй его в ту группу, которая содержит наименьший вес. |
| Автор: Lacoste1024 9.11.2011, 17:33 | ||
Этот вариант я тоже пробовал. Не подходит. Пример грузов: 25, 16, 9, 36, 41. Правильный ответ: 1я группа - 25+41=66. 2я группа - 16+9+36=61. При сортировке что по возрастанию, что по убыванию правильного ответа не получается. |
| Автор: math64 9.11.2011, 19:00 |
| Отсортировать по весам - правильное действие. Далее, определить общий вес и поделить пополам. Дальше нужно стремиться получить набор предметов весом менльше половины, как можно ближе к ней. Второй набор определиться автоматически. Если число предметов не превышает 32(64), набор опреляется числом uint32(uint64), в котором i-й бит устанавливается в 1 если i-й предмет включен в набор. Если предметов больше, нужно использовать bitset. |
| Автор: Silent 10.11.2011, 12:35 |
| Обычная динамика. Считаешь общий вес, находишь половину - это "идеальный вес", который должен быть. А дальше - классическая задача о камнях, нужно набрать не больше "идеального веса". Литература - Окулов, Программирование в алгоритмах, страница 101-102 |
| Автор: lamber 10.11.2011, 14:11 |
| способ предложенный math64 является правильным, остальные мульки с сортировками не верны, задача на полный перебор (если я не пру, то это как раз тот тип задач над решением, которых и стоит вопрос P!=NP или P==NP входит в одну из 10-ти задач тысячелетия, могу буровить если что знатоки поправьте ). Если ответ не получен могу скинуть исходник для решения подобных задач. |
