Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Работа с файлом

Автор: 3.14zDoS 1.12.2004, 17:57

Есть файл(НазваниеПредмета, Вес, Стоимость):
предмет1 1500 200
предмет2 2000 100
предмет3 1500 200
предмет4 2500 100
предмет5 1000 200
предмет6 2500 100
предмет7 1500 200
предмет8 500 100
Как наполнить StringGrid так чтобы не превышалась грузоподъемность(5000) а стоимость была максимальна.

Автор: ~FoX~ 2.12.2004, 11:12

3.14zDoS
Это тебе в раздел алгоритмы надо. smile

ИМХО самое простое полным перебором всех вариантов.

Автор: Snowy 2.12.2004, 13:35

Нужно отсортировать по признаку цена/вес. И загружать в порядке убывания, пока не будет перегруза. А там уже напихать что помельче...
Но если предметов не так много, то действительно можно перепробовать просто все комбинации - надежней будет.

Автор: ~FoX~ 2.12.2004, 14:45

Snowy
А вчем раздница?

3.14zDoS
По любому НП полная задача, кроме как полным перебором не решается.

Автор: Snowy 6.12.2004, 12:52

Если объем данных большой, то полный перебор может занять немало времени. Где-то достаточно не абсолютный вариант, а наиболее приближенный, но быстрый. Ибо перебор всех комбинаций это степень. И чем больше вариантов, тем больше времени это займет в геометрической прогрессии. А так только два прохода максимум, если не меньше. Если еще посидеть и подумать, то можно продумать еще более умный вариант. Но это нужно только если вариантов много.

Автор: markowww 7.12.2004, 01:01

Можно использовате перебор с возвратом. Должно выглядеть как то так (заранее извинюясь, если что напутал):

Код


procedure NextItem(i: integer);
var Weight, Cost, j: integer;
begin
   ItemSet:= ItemSet + [i];
   Weight:= CalculateWeight;
   if Weight <= MaxWeight then begin
      Cost:= CalculateCost;
      if Cost > MaxCost then begin
         MaxCost:= Cost;
         BestItemSet:= ItemSet;
      end;
      for j:= i + 1 to nmax do 
         NextItem(j);
   end;
   ItemSet:= ItemSet - [i];
end;

Здесь ItemSet, BestItemSet - множества, содержащие номера предметов текущей и наилучшей найденной комбинаций (set of integer); MaxWeight - максимально допустимый вес; MaxCost - цена наилучшей на данный момент комбинации. i - номер текущего предмета, nmax - количество предметов всего. CalculateWeight и CalculateCost - функции, подсчитывющие вес и цену текущей комбинации, заданной множеством ItemSet.

Алгоритм таков: на некотором шаге у нас есть комбинация с допустимым весом. К этой комбинации прибавляем следующий предмет, вызывая NextItem. Если вес остался допустимым, сравниваем стоимость текущей и лучшей комбинации и циклом добавляем следующий предмет (для перебора всех возможных последовательностей), в противном случае ничего не делаем. В любом случае вычитаем добавленный предмет: ведь если вес превысил максимльный, то любая другая комбинация, содеражщая текущую недопустима, а если не превысил, то мы, вызывая NextItem в цикле, уже проверили все комбинации с текущим предметом и осталось проверить комбинации без него.

Для работы запустить NextItem от номера первого элемента ( в принципе алгоритму не важно с какого номера начинается отсчет). Ну и конечно не забыть написать функции CalculateWeight и CalculateCost smile