Re: опять рюкзак

From

Valentin Davydov ()

To

Dmitry Zhadanoff

Date

2002-05-06T17:19:48Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: Dmitry Zhadanoff <Dmitry.Zhadanoff@p40.f1.n5095.z2.fidonet.org>
>   Date: Sun, 05 May 2002 20:44:29 +0400
>
>    А задача такая - есть рюкзак объемом float(любой real). Есть куча предметов
>массой тоже float. Необходимо набить рюкзак под завязку. Лучше - несколько
>наиболее подходящих вариантов загрузки. Объясните пожалуйста на пальцах (именно
>на пальцах) возможный алгоритм решения задачи.

Есть технология формирования таких особых начальных условий (масс и объёмов 
предметов), что оптимальный вариант можно найти только полным перебором. 
А для условий общего вида в большинстве случаев близкое к оптимуму решение
даёт "жадный" алгоритм: предметы сортируются по удельному весу и на каждом
шаге берётся самый плотный из тех, которые ещё лезут в рюкзак.

Вал. Дав.
--- ifmail v.2.15dev5
 * Origin: St. Petersburg State University (2:5020/400)