Bài Tập Chọn Lọc

Bài 1: {Bai toan Xep BALO (KNAPSACLE PROBLEM)
      * Co N hop kim loai trong luong Pi(KG) ,co gia ban la Vi (USD).Mot balo co
      the mang duoc M KG .Hay xac dinh ti le can lay o moi hop sao cho thu duoc
      1 Balo co gia tri nhat.
  Vi du:Co 3 hop sat
                                1       2        3
Khoi luong P =  18KG    15KG     10KG
Gia ban    V =  25USD   24USD    15USD
 M=20
Ta co nhung cach sap xep sau:
                         1        2         3       Value
P/an 1:      9KG      5KG       6KG
                        12,5USD   8USD     9 USD    29,5 USD
P/an 2:      9KG     10KG       1KG
                        12,5USD  16USD    1,5USD    30 USD
P/an 3:     0KG     15KG       5KG
                        0USD    24USD    7,5USD     31,5 USD
       Ta con rat nhieu phuong an de sap xep.Nhung cach xep de co duoc gia tri
nhieu nhat la XEP NHUNG HOP KIM LOAI MA GIA TRI CUA 1 KG LA LON NHAT vao truoc
  GIAI THUAT:Xep lai cac hop Kim loai,Hop nao ma gia tri 1 KG cao nhat thi xep
 truoc.Sau do bo tung hop vao cho den khi day Tui thi thoi.Ta co the tach KL
 cua hop ra}

Program Bai_toan_BALO;
Uses crt;
const N=5;
type arr=array[1..N]of byte;
var P,V,id:arr;{Khoi luong moi hop sat,Gia tri moi hop sat,Giu chi so}
       M:real;{Khoi luong tui xach}
{********************************************************************}
Procedure Input;
Var i:byte;
begin
write(`Khoi luong tui xach:`);readln(M);
write(`Do vat    :`);For i:=1 to n do write(i:5);
writeln;
write(`Khoi luong:`);for i:=1 to n do
                   begin
                         repeat
                              P[i]:=random(20);
                         until P[i]>0;
                   write(P[i]:5);
                   end;
writeln;
write(`Gia tri   :`);  for i:=1 to n do
                            begin
                         repeat
                                    V[i]:=random(20);
                         until V[i]>0;
                         write(V[i]:5);
                   end;
end;
{********************************************************************}
Procedure sortmax;
var i,j,temp:byte;
begin
 for i:=1 to n do id[i]:=i;
  for i:=1 to n-1 do
       for j:=i+1 to n do
            if V[id[j]]/P[id[j]]>V[id[i]]/P[id[i]] then
                    begin
                         temp:=id[i];
                         id[i]:=id[j];
                         id[j]:=temp;
                    end;
end;
{********************************************************************}
Procedure Output;
var i:byte;
begin
 write(`Do vat    :`);For i:=1 to n do write(id[i]:5);
 writeln;
 write(`Khoi luong:`);for i:=1 to n do write(P[id[i]]:5);
 writeln;
 write(`Gia tri   :`);  for i:=1 to n do write(V[id[i]]:5);
end;
{********************************************************************}
Procedure Control;
var Value,Temp,Cost:real;i:byte;
begin
i:=1;Value:=0;{Gia tri cua nhung hop duoc xep vao tui}
  repeat
      if P[id[i]]>=M then temp:=M else temp:=P[id[i]];
      Cost:=(V[id[i]]/P[id[i]])*temp;{Chua gia tri cua hop sat duoc chon de bo vao}
      writeln(`Vat thu `,id[i],` duoc chon:`);
      write(temp:0:3,`KG  `);writeln(cost:0:3,`$  `);
      value:=value+cost;
      M:=M-temp;
      inc(i);
  until (M=0) or (i=n+1);
  writeln(`Tong gia tri cua cac mat hang duoc chon:`,value:0:3,`$`);
end;
{********************************************************************}
Begin
  clrscr;
  Randomize;
  Input;
  writeln;
  Sortmax;
  writeln(`Cac do vat sau khi duoc sap xep:`);
  Output;
  writeln;
  Control;
readln;
end.

Bài