giup ve thuat toan rut tiền máy ATM

[hoangnam808]

cho mình hỏi :ví du minh muốn 1.290.000 thì máy sẻ cho ra 2 tờ 500, 2 tờ 100,1 tờ 50 và 2 tờ 20 .bạn nào biết dùng thuật toán nào ko, theo mình biết là họ dùng giải thuật tham lam thì phải

[fdoublef2008]

nếu giới hạn số tờ là max thi có thể dùng như sau
procedure atm(n:longint;var a,b,c,d:byte)
begin
for a:=max down to 0 do
for b:=max down to 0 do
for c:=max down to 0 do
for d:=max down to 0 do
if n=a*500000+b*100000+c*50000+d*20000 then exit;
end;
thuật toán này đơn giản nhưng không tối ưu

[picachusays]

thích tiền lẻ thì tới ngân hàng mà đổi
máy ATM dung tích đựng tiền có hạn nên nó chỉ trả tiển chẳn thoi

[jdkhang]

bài toán rút tiền ở máy ATM dùng thuật toán Quy hoạch động, minh họa ở các các bài toán ví dụ: rút tiền tối ưu số lượng tờ tiền rất nổi tiếng đó bạn.

[tuanrint]

Thầy em ra bài này, em cũng không làm được các anh hướng giúp cái

[nirvanat]

trời ơi. cái này dễ mà. mình lấy số tiền div 500 là được số tờ tiền loại 500. tương tự với các mệnh giá khác để tìm ra. có gì đâu. Còn nếu mà số tờ tiền rút là tối ưu ák. thì thì vẫn áp dụng được thuật tham lam nhưng chắc là sẽ có vài trường hợp sai ák. nên dùng quy hoạch động

[mini_bestboy]

Tham lam thì sẽ sai nhiều trường hợp. Nếu được thì dùng QHĐ là tối ưu nhất !
Mà nếu số tiền cần đổi không quá lớn bạn dùng quay lui cũng tốt đó :D

[jdkhang]

cho mình hỏi :ví du minh muốn 1.290.000 thì máy sẻ cho ra 2 tờ 500, 2 tờ 100,1 tờ 50 và 2 tờ 20 .bạn nào biết dùng thuật toán nào ko, theo mình biết là họ dùng giải thuật tham lam thì phải

Rảnh rỗi làm bài này vậy. Dùng phương pháp giải Quy hoạch động.

*Đặt lại bài toán: Có N loại tiền: 1, 2, 3, .., n; mỗi loại có 1 mệnh giá tương ứng là v[1] < v[2] < v[3] < ..< v[n]. Cho biết cách thanh toán cần ít số lượng tờ tiền nhất cho số tiền cần thanh toán là M.

Cách giải
Gọi F số lượng tờ tiền cần trả (cách trả cần ít tờ tiền nhất) có sử dụng i loại tờ tiền (1, 2, 3,.., i) cho số tiền j.
Giá trị cuối cùng: F[N, M] là kết quả của cách thanh toán; dùng N loại tờ tiền (1, 2, 3, ..., N) cho số tiền M.

*Công thức truy hồi: với việc chọn tối ưu số loại tiền 1, 2, 3, .., i để thanh toán số tiền j, F[i, j] sẽ có 2 khả năng:

[I]1). F = F[i-1, j]; Không dùng được loại tiền i để thanh toán số tiền j.
[I]2). F[i, j] = 1 + F[i, j-v[i]]; Có dùng loại tiền i để thanh toán số tiền j (đk: j >= v[i]).

F[i, j] là cách trả cần ít tờ tiền nhất, cho nên sẽ là min trong 2 giá trị thu được ở trên.

*Cơ sở quy hoạch động:
F[0, j] = vô cùng; (1<= j <= M) (quy định: nếu dùng các tờ tiền loại 0, có mệnh giá v[0] = 0 thì sẽ cần vô cùng tờ tiền mới thanh toán được cho số tiền j)

F[i, 0] = 0; (1<=i<=N) không có cách trả cho số tiền = 0.

*Chương trình minh họa:


{Quy Hoach Dong, Rut tien}
Program OptimizeCurrency;

Uses Crt;

Const NMax = 500; MMax = 65535;

Var currency : Array[1..NMax] of Word;
value : Array[1..NMax] of Word;
F : Array[0..NMax, 0..MMax] of Word;
N, M : Word;


Procedure Init;
Var i : Word;
Begin
Clrscr;

Write('Nhap so luong loai tien: '); Readln(N);

For i := 1 to N do
Begin
Write('Loai tien thu ', i, ' la: '); Readln(currency[i]);
value[i] := currency[i];
End;

Write('Nhap so luong tien muon thanh toan: '); Readln(M);

For i := 1 to M do
F[0, i] := M+1;

For i := 1 to N do
F[i, 0] := 0;
End;


Procedure Optimize;
Var i,j : Word;
Begin
For i := 1 to N do
For j := 1 to M do
Begin
F[i, j] := F[i-1, j];
If (j >= value[i]) And (F[i, j] >= 1 + F[i, j - value[i]]) Then
F[i, j] := 1 + F[i, j - value[i]];
End;
End;

Procedure Result;
Var i, j, c: Word;
Begin
If F[N, M] = M+1 Then
Writeln('Khong the thanh toan!')
Else
Begin
Writeln('So luong to tien can tra cho so tien ', M, ' la: ', F[N, M]);
Writeln('Cu the, cac loai to tien duoc thanh toan la: ');
i := N; j := M; c := 1;
While j > 0 do
Begin
If F[i, j] < F[i-1, j] Then
Begin
{Co dung loai tien i}
Writeln('To tien thu ', c , ' - loai: ', currency[i]);
j := j - value[i];
c := c + 1;
End
Else
Begin
{Khong dung loai tien i}
i := i - 1;
End;
End;

End;

Readln;
End;


BEGIN
Init;
Optimize;
Result;
END.


Bài toán trên vẫn chưa sát với thực tế (do số lượng tiền không giới hạn). Tuy nhiên chỉnh sửa 1 tí nữa, thêm số lượng cụ thể cho từng loại tờ tiền thì có thể sử dụng trong các máy ATM.
:D

[Long_Phung]

nếu giới hạn số tờ là max thi có thể dùng như sau


procedure atm(n:longint;var a,b,c,d:byte)
begin
for a:=max down to 0 do
for b:=max down to 0 do
for c:=max down to 0 do
for d:=max down to 0 do
if n=a*500000+b*100000+c*50000+d*20000 then exit;
end;

thuật toán này đơn giản nhưng không tối ưu

Như cách của bạn cũng OK nhưng sẽ cho ra nhiều kết quả.

Cách xác dịnh max của từng loại là:

- max từng tờ = số tiền còn lại div trị giá.

Bài này dùng đoạn sau thì sẽ tối ưu hơn.


......

If (sotien mod 10000)>0 then exit; {nếu không chia hết cho 10000}
so_to_500:=sotien div 500000;
so_to_200:=(sotien-so_to_500*500000) div 200000;
so_to_100:=(sotien-so_to_500*500000-so_to_200*200000) div 100000;
so_to_50 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000) div 50000;
so_to_20 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000-so_to_50*50000) div 20000;
so_to_10 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000-so_to_50*50000-so_to_20*20000) div 10000;
......

[jdkhang]

Cách xác dịnh max của từng loại là:

- max từng tờ = số tiền còn lại div trị giá.

Bài này dùng đoạn sau thì sẽ tối ưu hơn.


......

If (sotien mod 10000)>0 then exit; {nếu không chia hết cho 10000}
so_to_500:=sotien div 500000;
so_to_200:=(sotien-so_to_500*500000) div 200000;
so_to_100:=(sotien-so_to_500*500000-so_to_200*200000) div 100000;
so_to_50 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000) div 50000;
so_to_20 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000-so_to_50*50000) div 20000;
so_to_10 :=(sotien-so_to_500*500000-so_to_200*200000-so_to_100*100000-so_to_50*50000-so_to_20*20000) div 10000;
......


Cách giải này làm theo phương pháp tham lam, sẽ có những trường hợp bài toán sẽ không có lời giải mặc dù bài toán vẫn có lời giải.

[Long_Phung]

Bạn thử đưa ra trường hợp không có lời giải?
Với cách giải như trên, thì số tiền rút ra là tối ưu về số lượng tờ. và hoàn toàn không có giá trị nào là không có kết quả.
(Điều kiện của máy ATM là số tiền cần rút là bội số của 10000)

[jdkhang]

Với điều kiện bạn đưa ra như trên (trong máy luôn có tờ 10.000) thì tất nhiên luôn có lời giải.

Tuy nhiên, nếu vì 1 lý do nào đó, trong máy ATM loại tiền mệnh giá 10.000 không có thì sao?

Giả sử tôi cần rút: 60.000, trong máy chỉ có 2 loại tiền: 50.000 và 20.000 thì kết quả của thuật toán tham lam trên có ra lời giải không?