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

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

Форум программистов > Центр помощи > [Delphi] Задача о загрузке ТС

Автор: Klife 31.3.2009, 21:46

Делаю курсовик по мат. методам, вот тема: 'Решение задачи о загрузке транспортного средства методом динамического программирования" (она же задача о рюкзаке). Т. е. нужно найти оптимальный набор предметов который по массе не превышал бы грузоподъемности траспортного средства, а по стоимости был максимальным, методом динамического программирования. Взял отсюда функцию. Применил к своей программе эту функцию. Вроде заработала, а считает неправильно вот проверял по такой задаче:

m 11 17 23
p 20 36 48
Грузоподъемность=50
Три предмета где m-масса предмета, p-стоимость

Функция выдает результат 84, в действительности оптимальный набор такой (0,0,2) со стоимостью 96, не найду в чем причина?

Код


public
   koltov,gruz:integer;                             
   massto,masves:array[1..1000]of integer;

procedure TForm1.Button1Click(Sender: TObject);
var
i:integer;
begin
  koltov:=strtoint(edit1.Text);               
  gruz:=strtoint(edit2.Text);             
      for i:=1 to koltov do
        begin
          masves[i]:=strtoint(stringgrid1.cells[2,i]);
          massto[i]:=strtoint(stringgrid1.Cells[3,i]);
        end;
        showmessage(inttostr(Optium(gruz,koltov)));
end;

function TForm1.Optium(gruzkg,kol:integer):integer;
var
i,max,cost:integer;
const
k=2;
begin
  if kol=1 then
    begin
      if masves[1]<=gruzkg then optium:=massto[1]
      else optium:=0;
    end
  else begin
        max:=0;
        for i:=0 to k-1 do
          begin
            Cost:=i*massto[kol]+Optium((gruzkg-masves[kol])*i,kol-1);
            if Cost>Max then Max:=Cost;
          end;
  end;
  optium:=max;
end;