Skip to content

Instantly share code, notes, and snippets.

@max-kov
Last active May 21, 2020 18:18
Show Gist options
  • Save max-kov/96a0bfd7eef0f76fb25b to your computer and use it in GitHub Desktop.
Save max-kov/96a0bfd7eef0f76fb25b to your computer and use it in GitHub Desktop.
The rucksack problem solution in Pascal
program rucksack;
uses math;
type THistory = array [0..10000,0..10000] of integer;
tItem= record
val,size:integer;
end;
TItems = array [1..10000] of tItem;
var fin,fout: text;
maxSize,maxItems,curSize,counter,counter2:integer;
History:THIstory;
items: TItems;
begin
assign(fin,'in.txt');
reset(fin);
readln(fin, maxSize,maxItems);
for counter:=1 to maxITEMS do
readln(fin,items[counter].val,items[counter].size);
history[maxSize,maxItems]:=-1;
for counter:=1 to max(maxSize,maxItems) do begin
history[counter,0]:=0;
history[0,counter]:=0;
end;
counter:=1;
while (history[maxsize,maxItems]=-1) do begin
for counter2:=0 to items[counter].size-1 do
history[counter2,counter]:=history[counter2,counter-1];
curSize:=items[counter].size;
for counter2:=items[counter].size to maxSize do begin
history[counter2,counter]:=
max(curSize+history[maxSize-curSize,counter-1],
history[counter2,counter-1]);
writeln(history[counter2,counter]);
readln;
end;
writeln('############');
readln;
inc(counter);
end;
writeln(history[maxsize,maxItems]);
readln;
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment