//
you're reading...
Bài tập huấn luyện, Đề ôn luyện thi học kỳ

Bài tập huấn luyện: MÁY RÚT TIỀN MÁY ATM


Đề bài


new-picture

 

Lưu ý có các biến thể bài toán: số tờ giấy bạc có số lượng không hạn chế hay số lượng nhất định.


Hướng dẫn


Như ta đã biết, nghiệm của bài toán là một dãy nhị phân độ dài n, giả sử đã xây dựng được k thành phần (x1, x2, … ,xk), đã trả được sum và sử dụng c tờ. Để đánh giá được các nghiệm mở rộng của (x1, x2, … ,xk) ta nhận thấy:

  • Còn phải trả : S – sum.
  • Gọi tmax[k] là giá cao nhất trong các tờ tiền còn lại ( tmax [k] = max{tk+1, … , tn} thì ít nhất cần sử dụng thêm (S – sum)/ (tmax[k]) tờ nữa.

Do đó, nếu c +  (S – sum)/ (tmax[k]) mà lớn hơn hoặc bằng số tờ của cách trả tốt nhất hiện có
thì không cần mở rộng các nghiệm của
(x1, x2, … ,xk) nữa.


Chương trình


const MAX =20;
fi =’ATM.INP’;
fo =’ATM.OUT’;
type vector =array[1..MAX]of longint;
var t,tmax :array[1..MAX]of longint;
x,xbest :vector;
c,cbest :longint;
n,s,sum :longint;
procedure input;
var f :text;
i :longint;
begin
assign(f,fi); reset(f);
readln(f,n, s);
for i:=1 to n do read(f,t[i]);
close(f);
end;
procedure init;
var i :longint;
begin
tmax[n]:=t[n];
for i:=n-1 downto 1 do begin
tmax[i]:=tmax[i+1];
if tmax[i]<t[i] then tmax[i]:=t[i];
end;
sum:=0;
c:=0;
cbest:=n+1;
end;
procedure update;
var i :longint;
f :text;
begin
if (sum = s) and (c<cbest) then begin
xbest:=x;
cbest:=c;
end;
end;
procedure printResult;

var i :longint;
f :text;
begin
assign(f,fo); rewrite(f);
if cbest<n+1 then begin
writeln(f,cbest);
for i:=1 to n do
if xbest[i]=1 then write(f,t[i],’ ‘);
end
else write(f,’-1′);
close(f);
end;
procedure branchBound(i:longint);
var j :longint;
begin
if c + (s-sum)/tmax[i] >= cbest then exit;
for j:=0 to 1 do begin
x[i]:=j;
sum:=sum + x[i]*t[i];
c:=c + j;
if (i=n) then update
else if sum<=s then branchBound(i+1);
sum:=sum – x[i]*t[i];
c:=c – j;
end;
end;
BEGIN
input;
init;
branchBound(1);
PrintResult;
END.

Bộ test:

ATM.INP ATM.OUT
10 390
200 10 20 20 50 50 50 50 100 100
5
20 20 50 100 200

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

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: