|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Leonid Troyanovsky 2:5020/400 16 Oct 2001 09:21:55
To : Alexey Savyuk
Subject : задачка
--------------------------------------------------------------------------------
Alexey Savyuk wrote:
> сабж: Есть множество золотых самоpодков известного веса. Разделить самоpодки
> на 2 кучи, наиболее близкие по весу.
> Может кто-нидь поможит пpидумать алгоpитм pешения этой задачки ???
Задачу можно свести к ЗЛП (целочисленного|булева программирования)
Пусть A = a1 + ..+ an - общий вес
а Xi из {0, 1} - принадлежность к выборке.
Будем искать min:
R = A/2 - (a1*X1 + .. an*Xn);
при условии A/2 - (a1*X1+ ..+ an*Xn) >= 0
Далее, наверное, решать методом Гомори.
--
С уважением, LVT
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
