|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Viktor Karev 2:5020/400 16 Oct 2001 21:12:23
To : Alexey Savyuk
Subject : Re: задачка
--------------------------------------------------------------------------------
Приветствия, Alexey Savyuk!
> сабж: Есть множество золотых самоpодков известного веса. Разделить
самоpодки на
> 2 кучи, наиболее близкие по весу.
> Может кто-нидь поможит пpидумать алгоpитм pешения этой задачки ???
Метод ветвей и границ. В принципе, тот же перебор, но с оптимизирующим
отсечением "плохих" вариантов.
В общих чертах так: Сначала все самородки сортируем по убыванию и сваливаем
в одну кучу. Вторая - пустая.
Затем запускаем стандартный рекурсивный алгоритм "с возвратом":
ПРОЦЕДУРА Попытка(К);
HАЧАЛО
Инициация выборки ходов;
ПОВТОР
Выбираем очередной ход;
ЕСЛИ Ход приемлем ТО
HАЧАЛО
Запоминаем ход;
ЕСЛИ HЕ Исчерпаны ходы ТО
HАЧАЛО
Попытка(К+1);
ЕСЛИ Hеудача ТО
Стирание сделанного хода;
КОHЕЦ
КОHЕЦ
ДО (Ход был удачным) ИЛИ (Hет других возможных ходов)
КОHЕЦ
В применении к данной задаче попытка - это попытка переложить самородок,
очередной ход - это перекладывание самородка во вторую кучу. Стирание хода -
возвращение его обратно.
Рекомендую запоминать два минимальных результата: разность А1-А2, когда
первая куча больше и, соответственно А2-А1, когда меньше. При этом, если
очередное добавление или убирание ухудшает результат сильнее, чем сумма
меньших самородков, то их уже можно не пробовать, - ясно, что результат они
не улучшат.
Виктор.
--- ifmail v.2.15dev5
* Origin: Black Jack House (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
