//
you're reading...
Bài tập huấn luyện, Chủ đề quy hoạch động, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi

Chuyên đề: Quy hoạch động – Bài tập 01: Đổi tiền

[Đầu trang]]

[Nguồn] [Lời giải và các bộ Test]


Đề bài


Cho một ngân hàng có N loại tiền mệnh giá A[1],A[2],…A[N] với số lượng tiền mỗi loại không giới hạn . Cần chi trả cho khách hàng một số tiền M đồng . Hãy cho biết cần bao nhiêu tiền mỗi loại để chi trả sao cho số lượng tờ là ít nhất .

Dữ liệu vào từ file: Tien.Inp  như sau :

  • Dòng đầu tiên ghi 2 số N,M . ( N<=100,M<=10000)
  • Dòng thứ hai ghi N Số : A[1], A[2],…A[N]

Kết quả:    Ghi ra File : Tien.Out như Sau :

  • Dòng Đầu tiên ghi số tờ cần dùng. Nếu không thể đổi đựoc thì ghi số 0 và không cần thực hiện tiếp.
  • Dòng tiếp theo ghi số n số biểu hiện cho số tờ cần dùng cho mỗi loại.

Hướng dẫn


Chúng ta gọi Mind[I] là số lượng tờ ít nhất để trả số tiền I, như vậy bài toán yêu cầu chúng ta xác định Mind[M] . Ta nhận thấy rằng để được số tiền là I thì chúng ta sẽ có các cách để tạo thành số tiền đó khi chúng ta dùng thêm một tờ là : I-A[K1],I-A[K2],…I-A[KJ] ,Trong đó KJ là số thoả mãn mà A[KJ] < I. Vậy để số tiền tối ưu nhất là chúng ta cần tìm thấy trong các Mind[I-A[K1]]+1, Mind[I-A[K2]]+1, … , Mind[I-A[KJ]]+1 . Có công thức quy hoạch động như sau:

Mind[I]:=MinMind[I-A[J]]+1,  J  – thoả mãn : A[J]<I.

Từ đó chúng ta có thủ tục quy hoạch động như sau :

Procedure Quy_Hoach_Dong;
Begin
    Mind[0]:=0;
    For I:=1 To M Do
        Begin
             Min:=Maxint;
             For J:=1 To N Do
             If (Mind[I-A[J]]+1<Min)And (A[J]<I) Then
                 Begin
                    Min:=Mind[I-A[J]]+1;
                    Luu[I]:=J;
                 End;
             Mind[I]:=Min;
        End;
End;

Trong đó mảng Luu là mảng chứa đựng loại tiền nào cần dùng cuối cùng để đến số tiền I. Như vậy chúng ta có cách để tìm lại các loại tiền cần dùng bằng mảng Luu như sau :

J:=Luu[M];
I:=M;
While J0 Do
    Begin
        Write(A[J]);
        I:=I-J;
        J:=Luu[I];
    End;

Như vậy chúng ta sẽ giải quyết bài toán trên một cách ngắn gọn và đơn giản. Để tăng tính tự sáng tạo của các bạn, kể từ bài toán sau chúng tôi chỉ nêu qua các thủ tục và công thức quy hoạch động. Nếu các bạn không giải quyết được vấn đề nhỏ đó thì có thể tham khảo phần lời giải của chúng tôi. Tiếp sau đây là một loạt bài toán tương tự bài toán 1, mà thực chất chúng chỉ là một dạng bài cố định, nó chỉ biến dạng đi về lời lẽ nhưng đều giống nhau về bản chất .


Lời giải


program         Qhd_01 ;
uses            crt ;
const
    fi =       'Tien.Inp' ;
    fo =       'Tien.Out' ;
Var
    mind , luu   :       array [ 0..10000 ] of word ;
    n , m        :       integer ;
    a , sl       :       array [ 1..100 ] of integer ;

procedure          readfile ;
var
    f       :       text ;
    i       :       integer ;
begin
    assign ( f , fi ) ;
    reset ( f ) ;
    readln ( f , n , m ) ;
    for i := 1 to n do
        read ( f , a [ i ] ) ;
    close ( f );
end ;

procedure          quy_hoach_dong ;
var
    i , j , min     :       word ;
begin
    Mind [ 0 ] := 0 ;
    luu [ 0 ] := 0 ;
    For i:=1 to m do
        begin
            luu [ i ] := 2 * maxint ;
            min := 2 * maxint ;
            for j :=1 to n do
              if a [ j ]  mind [ i - a [ j ] ] + 1 then
                   begin
                      luu [ i ] := j ;
                      min := mind [ i - a [ j ] ] + 1 ;
                   end ;
            mind [ i ] := min ;
        end ;
end ;

procedure          writefile ;
var
    f       :       text ;
    i , j   :       integer ;
begin
    assign ( f , fo );
    rewrite ( f ) ;
    if mind [ m ] = 2 * maxint then
        begin
            writeln ( f , -1 );
            close ( f ) ;
            halt ;
        end ;
    writeln ( f , mind [ m ] ) ;
    j := luu [ m ] ;
    i := m ;
    fillchar ( sl , sizeof ( sl ) ,0 ) ;
    while j0 do
        begin
            inc ( sl [ j ] ) ;
            i := i - a [ j ] ;
            j := luu [ i ] ;
        end ;
    for i := 1 to  n do
        write ( f , sl [ i ] ,' ' ) ;
    close ( f ) ;
end ;

Begin
    readfile ;
    quy_hoach_dong ;
    writefile ;
End.

Tham khảo thêm


  1. Bài toán đổi tiền
  2. _
  3. _

[Về đầu trang]]

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: