ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vasily Shmelev                       2:5020/400     11 Jul 2001  10:14:54
 To : Sergey Radkevitch
 Subject : Re: fractional knapsack problem
 -------------------------------------------------------------------------------- 
 

 
 Hello! Sergey Radkevitch wrote in message:
 
 SR> Есть N разновидностей предметов, число предметов каждой разновидности
 SR> ограничено Ki. Каждый тип предметов имеет вес Vi. Hужно найти такое
 SR> подмножестао предметов, чтобы их суммарный вес максимально приближался
 
 снизу
 
 SR> к фиксированному весу W, а количество использованных типов было
 
 минимально.
 
 SR> Предметов ~635, разновидностей ~10.Как это сделать?
 
     Отсортировать массив типов по убыванию, а затем начать подбирать:
 * если cW (текущий вес) + 1-ый элемент в отсортированном массиве < W,
   тогда прибавляем и вычитаем из массива количества предметов каждого типа
 1.
 * если > W, тогда смотрим следующий элемент. Тоже самое, если такие предметы
   кончились.
 * если дошли до конца списка, то задача решена.
 
     Могу написать исходник на C или Pascal. Только задачу уточни, чтообы
 было понятно, что писать.
 
 --
 С уважением, Василий
 
 ..."Push to test."  <click>  "Release to detonate." (from Bruce Graham)
 --- ifmail v.2.15dev5
  * Origin: йПЮЯМHОHОЕПЕВМШЕ ОHОСЦЮИВХЙХ (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    fractional knapsack problem   Sergey Radkevitch   19 Jun 2001 15:25:06   Re: fractional knapsack problem   Vasily Shmelev   11 Jul 2001 10:14:54