Рюкзак на Delphi

[serg268]

Мы собираемся в поход, имея рюкзак объема V и неограниченный запас каждого из N различных видов предметов. Каждый предмет i имеет известный объем vi и стоимость mi , i = 1, …, N. В рюкзак можно положить целое число различных предметов. Нужно напи-сать ПС упаковки рюкзака так, чтобы общая стоимость упакованных предметов была наибольшей, а их общий объем не превосходил V. Формой предметов пренебречь.

[Stilet]

Где-то я уже видел тут программы по расчету упаковок.

[serg268]

Народ дело в том что прогу необходимо написать на Delphi , а я с этим языком никогда несталкивался, а времени разбираться нет.... Если у кого есть идеи по коду.... заранее спасибо

[KobolD]

Я, к сожалению, тоже не знаком с делфи, а решение такое.
Создается масив [n, 1...3]в строках у которого распологаются предметы, в первом столбце - объем, во втором - стоимость.
В третьей столбец вычисляем стоимость единицы объема каждого предмета (второе делим на первое).
Сортируем масив по третьему столбцу, по убыванию. Получается что первый элемент получается самый ценный по соотношению цена/объем.
Начинаем "запихивать вещи в рюкзак" с первого элемента масива по принципу если объем текущей вещи меньше(или равен) чем оставшийся объем рюкзака то запихиваем ее туда, если нет то переходим на след элемент. Тут надо использовать цикл while вместо For т.к. одну вещь можно положить в рюкзак несколько раз.