Xếp ba lô

Bài 5.3. Xếp ba lô

           Có N vật (mặt hàng), với mỗi vật ta biết trọng lượng và giá trị của nó. Hãy xác định trọng lượng cần lấy ở một số vật để xếp vào một ba lô có sức chứa tối đa là M sao cho giá trị chứa trong ba lô là lớn nhất. Giả thiết là có thể lấy một tỉ lệ tuỳ ý ở mỗi vật.

Dữ liệu vào: Tệp văn bản balo.inp:

-          Dòng đầu tiên: hai giá trị nguyên dương N và M.

-          N dòng tiếp theo, mỗi dòng chứa hai giá trị nguyên dương d v cho mỗi vật, trong đó d là trọng lượng, v là giá trị tính theo một đơn vị trọng lượng của vật đó (đơn giá). Các số cách nhau qua dấu cách.

BALO.INP 5 30 8 5 5 4 4 2 3 8 16 6

Có N = 5 vật và sức chứa tối đa của ba lô là M = 30 (kg). -       Vật thứ nhất có trọng lượng 8, đơn giá  5 tr/kg, -       Vật thứ hai có trọng lượng 5, đơn giá 4, -       Vật thứ ba có trọng lượng 4, đơn giá 2, -       Vật thứ tư có trọng lượng 3, đơn giá 8, -       Vật thứ năm có trọng lượng 16, đơn giá 6. (tr. -  triệu đồng)

BALO.OUT    8    3    0    3    16    172

Dữ liệu ra: Tệp văn bản tên balo.out:

-          N dòng, dòng thứ i cho biết trọng lượng cần lấy ở vật thứ i.

-          Dòng cuối cùng ghi tổng giá trị thu được.

Hướng dẫn

Có nhiều bài toán thuộc họ xếp ba lô, thuật toán cho bài này thuộc lớp tham lam.

Dễ thấy tiêu chuẩn chọn là giá đơn vị cao. Ta duyệt các vật theo giá đơn vị từ cao trở xuống. Vật được chọn sẽ được lấy tối đa. Như vậy, nếu tổng trọng lượng các vật bằng hoặc lớn hơn sức mang của ba lô thì bao giờ ba lô cũng được xếp đủ.

(*  Pascal  *)

(*--------------------------------

            BALO.PAS

---------------------------------*)

program balo;

uses crt;

const

  MN = 200;

  fn = 'BaLo.inp';      gn = 'BaLo.out';

var

      a,id: array[1..MN] of integer;{a[i] tr lg vat i}

      gdv: array[1..MN] of integer; {gdv[i] don gia vat i}

f, g: text;

n,m: integer; {n: so vat; m: trong luong balo}

t,tt: integer;

{t: tong trong luong con duoc xep vao balo}

{tt: tong gia tri da lay}

(*----------------------------------

            Doc du lieu

-----------------------------------*)

procedure Doc;

var i,k: integer;

begin

assign(f,fn); reset(f); readln(f,n,m);

for i :=  1 to n do read(f,a[i],gdv[i]);

close(f);

end;

(*------------------------------------

         Khoi tri cho chi dan

--------------------------------------*)

procedure InitID;

var i: integer;

begin

for i := 1 to n do id[i] := i;

end;

(*--------------------------------------

        Sap giam theo gia don vi

----------------------------------------*)

procedure IDQuickSort(d,c: integer);

var i, j, k, x: integer;

begin

i := d; j := c;

x := gdv[id[(i+j) div 2]]; {phantu giua}

while i <= j do

begin

while gdv[id[i]] > x do inc(i);

while gdv[id[j]] < x do dec(j);

if i <= j then

    begin

          k := id[i];

          id[i] := id[j];

          id[j] := k;

          inc(i); dec(j);

    end;

end;

if d < j then IDQuickSort(d,j);

if i < c then IDQuickSort(i,c);

end;

procedure XepBaLo;

var i: integer;

begin

tt := 0; {tong gia tri }

t := m; {trong luong con lai cua balo }

for i :=1 to n do

if t >= a[id[i]] then

begin { lay tron vat id[i] }

    t := t-a[id[i]];

    tt :=  tt + (a[id[i]]*gdv[id[i]]);

end

else { lay cho day balo }

begin

    tt :=  tt+(t*gdv[id[i]]); {lay vua du }

    a[id[i]] :=  t; {chinh lai vat cuoi }

    t := 0;

end;

end;

procedure Ghi;

var i: integer;

begin

assign(g,gn);  rewrite(g);

for i := 1 to n do writeln(g,a[i]);

writeln(g,tt); close(g);

end;

BEGIN

Doc; InitID; IDQuickSort(1,n);

XepBaLo; Ghi;

END.