Tin học 11

[maiminhtien]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

cho hỏi thuật toán làm bài này:

một người mua hàng cần trả N đồng, người đó có các loại giấy bạc T1,T2,...,Tm. Hãy cho biết người đó có bao nhiêu cách trả tiền và cách nào tốn ít giấy bạc nhất?

 

[dung_bao_gio_tu_bo_uoc_mo_cho_du_ban_la_ai_di_nua]

Quy hoạch động

lập bảng quy hoạch giống bài xếp đồ vật vào túi

 

[p_trk]

đây là bài toán rút tiền ATM . hoặc trả tiền như bạn nói !!
MONEY.INP

 10 390
200 10 20 20 50 50 50 50 100 100

MONEY.OUT

 5
   200   100   50   20   20

dưới đây là code chương trình !!

 const fi='MONEY.INP'; fo='MONEY.OUT';
 VAR
   n,s,x: word;
   a,kq:array[1..100] of word;

   procedure nhap;
   var
     f: text;
     i:word;
   begin
      assign(f,fi);reset(f);
      read(f,n,s);
      for i:=1 to n do
       read(f,a[i]);
   end;
  {------------------------}

  procedure sort;
   var
     i,j,t: word;
   begin
       for j:=n downto 2 do
        for i:=1 to j-1 do
         if a[i]<a[i+1] then
          begin
            t:=a[i];
            a[i]:=a[i+1];
            a[i+1]:=t;
          end;
   end;
  {--------------------------}
  procedure xuat;
    var
      f: text;
      i: word;
    begin
       assign(f,fo); rewrite(f);

       if S<>0 then
        write(f,-1 ) else
         begin
             writeln(f,x);
             for i:=1 to x do
               write(f,'   ',kq[i] );
         end;

        close(f);
    end;

  {---------------------------}
  procedure xd;
   var i: word;
   begin
       i:=1;
       x:=0;
     while i<=n do
      begin
       if a[i]>S then inc(i) else
       if a[i]=S then
        begin
            S:=S-a[i];
            inc(x);
            kq[x]:=a[i];
            exit;
       end else
       if a[i]<S then
        begin
           inc(x);
           kq[x]:=a[i];
           S:=S-a[i];
           inc(i)
        end
      end;
   end;
  { ------------------------}
BEGIN
       nhap;
       sort;
       xd;
       xuat;
 END.

Chúc bạn học tốt ! mà bạn học chuyên tin à !!