Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Friday, January 17, 2014



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 NM.
-          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.

0 comments:

Post a Comment

Popular Posts