Trả tiền

Có N loại tiền mệnh giá m_i và số lượng s_i , i = 1..N. Xác định số lượng mỗi loại để có thể trả lại V đồng.

TRATIEN.INP	TRATIEN.OUT
6 156 1 2 5 10 20 50 4 7 2  3  6  2	0 3 0 0 5 1

  Dữ liệu vào: tệp văn bản TRATIEN.INP

  Dòng đầu tiên: hai số tự nhiên N và V, 2 £ N £ 15.

  Dòng thứ hai: N số tự nhiên m₁, m₂,…,m_N.

  Dòng thứ ba: N số tự nhiên s₁, s₂,…,s_N.

  Dữ liệu ra: tệp văn bản TRATIEN.OUT

  N số tự nhiên c₁, c₂,…,c_N thể hiện số lượng tờ tiền mỗi loại cần trả, c₁m₁ + c₂m₂ + …+ c_Nm_N = V. Nếu vô nghiệm: ghi số 0.

Trong các tệp *.INP và *.OUT các số trên cùng dòng cách nhau qua dấu cách.

Thuật toán

Đây là loại toán Balo với dữ liệu nhỏ vì trong thực tế số mệnh giá không nhiều, thí dụ, tiền Việt chỉ có các loại sau đây là thông dụng 100, 200, 500, 1.000, 2.000, 5.000, 10.000, 20.000, 50.000, 100.000,  200.000, 500.000. Nếu tính theo đơn vị 100 đồng thì ta có thể viết lại dãy trên cho gọn hơn như sau:

1, 2, 5, 10, 20, 50, 100, 200, 500, 1.000,  2.000, 5.000.

Ta duyệt các tổ hợp số tờ tiền phải trả cho mỗi loại mệnh gía, cận dưới là 0 cận trên là min(s_i, v div m_i) vì để trả lại v đồng bằng loại mệnh giá m_i ta dùng tối đa (v div m_i) tờ.

Độ phức tạp: (b₁-a₁+1)(b₂-a₂+1)...(b_v-a_v+1), v = M+N.

Chú ý: Sau này ta sẽ xây dựng thuật toán tốt hơn cho bài toán trả tiền. Thuật toán này dựa  trên một số kiến thức số học.

(*  Pascal  *)

(****************************************

                Tra tien

*****************************************)

program TraTien;

uses crt;

const mn = 20; bl = #32; nl = #13#10;

    fn = 'TRATIEN.INP'; gn = 'TRATIEN.OUT';

type mi1 = array[0..mn] of integer;

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

    n – so luong cac loai tien

    v – so tien can tra lai

    vt – gia tri tam thoi

    m[1..n] – cac menh gia

    s[1..n] – so luong to tien

    c[1..n] – so luong can chon

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

var n,v,vt: integer;

   m,s,c: mi1;

   f,g: text;

procedure Doc;

  var i: integer;

begin

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

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

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

  close(f);

end;

function Min(a,b: integer): tự viết

function Next: Boolean;

  var i: integer;

begin

  Next := false;

  i := n;

  while (c[i] = s[i]) do

    begin

      vt := vt - c[i] * m[i];

      c[i] := 0;

      i := i - 1;

    end;

  if (i = 0)  then exit;

  c[i] := c[i] + 1;

  vt := vt + m[i];

  Next := true;

end;

function Duyet: Boolean;

  var i: integer;

begin

  { Khoi tri }

  for i := 1 to n do

   begin

     s[i] := min(s[i],v div m[i]);

     c[i] := 0;

   end;

  c[0] := -1;  vt := 0; { tong gia tri cua 1 phuong an }

  Duyet := true;

  repeat

    if (vt = v) then exit;

  until not Next;

  Duyet := false;

end;

procedure Run;

  var i: integer;

begin

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

  if (Duyet) then

     for i := 1 to n do write(g,c[i],bl);

    else writeln(g,0);

  close(g);

end;

BEGIN

  Run;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH