Прога

From

Anton Kuznetsov (2:5030/566.13)

To

Boris Sivko

Date

2002-12-03T21:12Z

Area

RU.ALGORITHMS

                Всех тебе благ, Boris!


 RT>> 2. Имеется M различных предметов, известны вес каждого предмета и его
 RT>> стоимость. Определить какие предметы надо выбрать, чтобы общий вес не
 RT>> превышал 50, а стоимость общая стоимость была максимальна.
 BS> Эвристика: жадный алгоритм.

 Ну она совсем плохая для примера:

 вес цена
 49  49
 25  25
 25  25

 Это не работает...

 BS> Наверняка: полный перебор с отсечениями.

 Ну вообщем метод ветвей и границ...

 Рекурсия... По всем элементам и для каждого смотришь брать или нет, а если
взять и сумма веса перевалит за 50 - то вылезаешь... + зная текущее
максимальное значение стоимости скажем К и сумму того что получается на данный
момент О смотришь если попытаться добить оставшийся вес предметом с
максимальной плотностью (отношение цены к массе), то получится меньше К - то
тоже вылезаешь...

 А вообще в любой нормальной книжке это называется "Задача про Рюкзак" - и в
любой книжке она разобрана...

                            До свидания, Boris!
 * Origin: ФТШ - школа наша! (2:5030/566.13)