//
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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười Một 2016
H B T N S B C
« Th10   Th12 »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Thống kê

  • 254,200 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: