ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Kuznetsov                      2:5030/566.13  03 Dec 2002  22:12:00
 To : Boris Sivko
 Subject : Прога
 -------------------------------------------------------------------------------- 
 

 
 
  RT>> 2. Имеется M различных предметов, известны вес каждого предмета и его
  RT>> стоимость. Определить какие предметы надо выбрать, чтобы общий вес не
  RT>> превышал 50, а стоимость общая стоимость была максимальна.
  BS> Эвристика: жадный алгоритм.
 
  Hу она совсем плохая для примера:
 
  вес цена
  49  49
  25  25
  25  25
 
  Это не работает...
 
  BS> Hаверняка: полный перебор с отсечениями.
 
  Hу вообщем метод ветвей и границ...
 
  Рекурсия... По всем элементам и для каждого смотришь брать или нет, а если
 взять и сумма веса перевалит за 50 - то вылезаешь... + зная текущее
 максимальное значение стоимости скажем К и сумму того что получается на данный
 момент О смотришь если попытаться добить оставшийся вес предметом с
 максимальной плотностью (отношение цены к массе), то получится меньше К - то
 тоже вылезаешь...
 
  А вообще в любой нормальной книжке это называется "Задача про Рюкзак" - и в
 любой книжке она разобрана...
 
                             До свидания, Boris!
  * Origin: ФТШ - школа наша! (2:5030/566.13)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Прога   Roman Tuchegromoff   02 Dec 2002 01:26:40   Re: Про   Anthony Volkov   02 Dec 2002 06:08:04   Прога   Moderator   02 Dec 2002 13:25:12   Прога   Boris Sivko   02 Dec 2002 23:53:06   Прога   Anton Kuznetsov   03 Dec 2002 22:12:00   Прога   Boris Sivko   06 Dec 2002 19:56:17   Прога   Denis Artuhov   05 Dec 2002 06:23:48   Re: Прога   Valentin Davydov   05 Dec 2002 18:38:08