Bài toán đổi tiền

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (47.63 KB, 2 trang )

Bài toán Đổi tiền: Giả sử trong kho bạc có N loại tiền có mệnh giá lần lượt là
D[1], D[2], , D[N] đơn vị. Muốn đổi một lượng tiền M đơn vị. Hỏi phải đổi như thế
nào để có số tờ tiền là ít nhất.
Dữ liệu vào:
Nhâp vao 2 so N, M.
Nhập vào N số : D[1], D[2],…,D[n].
Gọi minD[I] là số lượng tờ tiền í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 thêm một tờ là:
I-D[K1], I-D[K2],…, I-D[KJ], trong đó KJ là số thỏa mãn mà D[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-D[K1]]+1, minD[I-D[K2]]+1,
… , minD[I-D[KJ]]+1. Có công thức quy hoạch động như sau:
minD[I]:=Min(minD[I-D[J]]+1), J thỏa mãn: D[J]<I.
Từ đó chúng ta có thủ tục quy hoạch động như sau:
quyHoachDong{
minD[0]:=0;
for(int I=1;i<=M;i++){
Min:=maxint;
If ((minD[I-D[J])+1< Min) && (D[J]<I){
Min:=minD[I-D[J]]+1;
Luu[I]:=J;
}
minD[I]:=Min;
}
}
Trong đó mảng Luu là mảng chứa các 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(J!=0){
Printf(D[J]);

I:=I-J;
J:=Luu[i];
}

Tài liệu liên quan

Bài toán đổi tiền

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về