HomeQUY HOẠCH ĐỘNG
Thứ Bảy, 1 tháng 7, 2017
Phương
pháp quy hoạch động dùng để giải bài toán tối ưu có bản
chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm
phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán
đệ quy chúng ta đã tìm hiểu, nguyên lý chia để trị (divide and conquer) thường
đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con cùng dạng
với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên
lý này càng được thể hiện rõ: Khi không biết cần phải giải quyết những bài toán
con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải
hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để
giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy
hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch
động:
Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành
nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con
lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp
bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
Quy
hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất ( bài toán cơ sở)
để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài
toán lớn nhất (bài toán ban đầu).
Ta
xét một ví dụ đơn giản:
Dãy
Fibonacci là dãy vô hạn các số nguyên dương F[1], F[2], … được định nghĩa như
sau:
1, if i ≤ 2
F[ i ] = { F[ i −1] + F[ i − 2],
if i ≥ 3
Hãy
tính F[6]
Xét
hai cách cài đặt chương trình:
Cách 1
|
Cách 2
|
|
program Fibo1;
|
program Fibo2;
|
|
function F(i: Integer):
Integer;
|
var
|
|
F:
array[1..6] of Integer;
|
||
begin
|
i: Integer;
|
|
if i < 3 then F := 1
|
begin
|
|
else F := F(i - 1) + F(i -
2);
|
||
end;
|
F[1] :=
1; F[2] := 1;
|
|
begin
|
for i := 3 to 6 do
|
|
F[i] :=
F[i - 1] + F[i - 2];
|
||
WriteLn(F(6));
|
WriteLn(F[6]);
|
|
end.
|
end.
|
|
Cách
1 có hàm đệ quy F(i) để tính số Fibonacci thứ i. Chương trình chính gọi F(6),
nó sẽ gọi tiếp F(5) và F(4) để tính … Quá trình tính toán có thể vẽ như cây
dưới đây. Ta nhận thấy để tính F(6) nó phải tính 1 lần F(5), hai lần F(4), ba
lần F(3), năm lần F(2), ba lần F(1).
Cách 2 thì không như vậy.
Trước hết nó tính sẵn F[1] và F[2], từ đó tính tiếp F[3], lại tính tiếp được
F[4], F[5], F[6]. Đảm bảo rằng mỗi giá trị Fibonacci chỉ phải tính 1 lần.
(Cách 2 còn có thể cải tiến thêm nữa, chỉ cần dùng 3 giá trị
tính lại lẫn nhau)
Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem
phương pháp đó có thoả mãn những yêu cầu dưới đây hay không:
Bài toán lớn phải phân rã
được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó
cho ta lời giải của bài toán lớn.
Vì quy hoạch động là đi giải
tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải
(bộ nhớ, đĩa…) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể
thực hiện được.
Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu
phải qua hữu hạn bước.
Các khái niệm:
- Bài toán giải theo phương pháp quy
hoạch động gọi là bài toán quy hoạch
động
- Công thức phối hợp nghiệm của các
bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi (hay phương trình truy toán) của quy hoạch động
- Tập các bài toán nhỏ nhất có ngay
lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động
- Không gian lưu trữ lời giải các bài
toán con để tìm cách phối hợp chúng gọi là bảng
phương án của quy hoạch động
Các bước cài đặt một chương trình sử dụng quy hoạch động:
- Giải tất cả các bài toán cơ sở
(thông thường rất dễ), lưu các lời giải vào bảng phương án. Dùng công thức truy
hồi phối hợp những lời giải của những bài toán nhỏ đã lưu trong bảng phương án
để tìm lời giải của những bài toán lớn hơn và lưu chúng vào bản phương án. Cho
tới khi bài toán ban đầu tìm được lời giải.
- Dựa vào bảng phương án, truy vết tìm
ra nghiệm tối ưu.
Cho đến nay, vẫn chưa có một định lý nào cho biết một cách chính xác
những bài toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy
nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có
thể tự đặt câu hỏi: “Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu của
các bài toán con hay không ?” và “Liệu
có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào đó để
phối hợp tìm được nghiệm bài toán lớn"
Bài toán 4: Xâu con chung dài nhất (như bài trên)
f[0,j]:=0;
for i:=1 to n do
for j:=1 to m do
if w[i]<=j then
f[i,j]:=max(f[i-1,j],f[i-1,j-w[i]]+v[i])
else f[i,j]:=f[i-1,j];
write(fo,f[n,m]);
Bài toán 7: Đổi tiền
Bài toán 8: Bố trí phòng họp
Bài toán 9: Cho thuê máy
Bài toán 10: Tiền khách sạn
MỘT SỐ BÀI TOÁN QHĐ CƠ BẢN
Bài toán 1: Dãy con đơn điệu tăng dài nhất:
Cho dãy A gồm n số nguyên, ký hiệu [a0, a1,..., an-1] . Tìm một
dãy con đơn điệu tăng dài nhất của dãy A, biết một dãy con của A là dãy có được
từ A bằng cách xóa đi một số phần tử của A.
Ví dụ: dãy [1, 5, 9, 2, 3, 11, 8, 10, 4] có dãy con đơn điệu tăng
dài nhất là [1, 2, 3, 8, 10].
Input: đọc từ tệp Day.inp gồm các số nguyên trong dãy A được viết cách nhau bởi dấu cách
Output: Ghi kết quả tính được vào tệp Day.out gồm 2 dòng
- Dòng 1: ghi độ dài của dãy con dài nhất
- Dòng 2: Ghi lần lượt từng phần tử của dãy con.
Cách giải:
Bổ sung vào a 2 phần tử a[0]=-∞ và a[n+1]=+∞ khi đó dãy đơn điệu dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc ở a[n+1]
với ∀ i 0 ≤ i ≤ n+1. ta tính L[i] bằng độ dại dãy con đơn điệu tăng dài nhất bắt đầu tại a[i].
* cơ sở QHĐ
L[n+1]=1 vì dãy này chỉ gồm 1 phần tử là +∞
* Công thức truy hồi
Cách 1: Duyệt từ cuối dãy về đầu dãy
Bổ sung vào a 2 phần tử a[0]=-∞ và a[n+1]=+∞ khi đó dãy đơn điệu dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc ở a[n+1]
với ∀ i 0 ≤ i ≤ n+1. ta tính L[i] bằng độ dại dãy con đơn điệu tăng dài nhất bắt đầu tại a[i].
* cơ sở QHĐ
L[n+1]=1 vì dãy này chỉ gồm 1 phần tử là +∞
* Công thức truy hồi
Giả sử với i chạy từ n về 0, ta cần tính L[i]: độ
dài dãy con tăng dài nhất bắt đầu tại a[i]. L[i] được tính trong điều kiện
L[i+1..n+1] đã biết:
Dãy con đơn
điệu tăng dài nhất bắt đầu từ a[i] sẽ được thành lập bằng cách lấy a[i] ghép
vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí
a[j] đứng sau a[i]. Ta sẽ chọn dãy nào để ghép a[i] vào đầu? Tất nhiên là chỉ
được ghép a[i] vào đầu những dãy con bắt đầu tại a[j] nào đó lớn hơn a[i] (để
đảm bảo tính tăng) và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép a[i] vào đầu (để
đảm bảo tính dài nhất). Vậy L[i] được tính như sau: Xét tất cả các chỉ số j trong khoảng từ i + 1 đến
n + 1 mà a[j] > a[i], chọn ra chỉ số jmax có L[jmax] lớn nhất. Đặt L[i] :=
L[jmax] + 1:
L [i ] = max L [ j] +1
i < j≤ n −1
a [ i ]< a [ j]
* Truy vết
Tại bước xây dựng dãy L, mỗi khi
gán L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng:
Dãy con dài nhất bắt đầu tại a[i]
sẽ có phần tử thứ hai kế tiếp là a[jmax].
Sau khi tính xong hay dãy L và T, ta bắt đầu từ
T[0]. T[0] chính là phần tử đầu tiên được chọn, T[T[0]] là phần tử thứ hai được
chọn, T[T[T[0]]] là phần tử thứ ba được chọn …
Quá trình truy vết có thể diễn tả
như sau:
i := T[0];
while i
<> n + 1 do
{Chừng nào chưa duyệt đến số a[n+1]=+∞ ở cuối} begin
{Chừng nào chưa duyệt đến số a[n+1]=+∞ ở cuối} begin
<Thông báo
chọn a[i]>
i := T[i];
end;
Ví dụ: với A = (5, 2, 3, 4, 9,
10, 5, 6, 7, 8). Hai dãy L và T sau khi tính sẽ là:
i
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
||||
ai
|
− ∞
|
5
|
2
|
3
|
4
|
9
|
10
|
5
|
6
|
7
|
8
|
+ ∞
|
||||
L[i]
|
9
|
5
|
8
|
7
|
6
|
3
|
2
|
5
|
4
|
3
|
2
|
1
|
||||
T[i]
|
2
|
8
|
3
|
4
|
7
|
6
|
11
|
8
|
9
|
10
|
11
|
|||||
Const Max = 5000;
Var a,L,T:array [0..Max] of integer;
i,j,n,jmax:integer; fi,fo:text;
Procedure
Nhapdulieu;
begin
assign(fi,'day.inp'); reset(fi); N:=0;
while not eof (fi) do
begin
N:=N+1; read(fi,a[N]);
end;
close(fi);
end;
BEGIN
assign(fo,'day.out'); rewrite(fo);
Nhapdulieu;
a[0]:= low(integer);a[n+1]:=high(integer);
{thêm 2 phần tử canh 2 đầu dãy}
L[n+1]:= 1; {Khởi tạo cơ sở QHĐ}
for i:= n downto
0 do {tính bảng phương án}
begin
{chọn trong các chỉ số j đứng sau i thỏa mãn
a[j]>a[i] chọn ra jmax có L[jmax] lớn nhất}
jmax:=n+1;
for j:=i+1 to n+1 do
if (a[i]<a[j]) and (L[j]>L[jmax])
then jmax:=j;
L[i] := L[jmax]+1; {lưu độ dài dãy tăng
dài nhất tại ai}
T[i] := jmax; {lưu vết: phần tử đứng liền sau a[i] trong dãy con tăng dài nhất đó là a[jmax]}
end;
Writeln(fo,L[0]-2); { độ dài dãy con
tăng dài nhất =L[0]-2 }
i:=T[0]; {bắt đầu truy vết tìm nghiệm}
while i<>n+1 do
begin
write(fo,a[i],' '); i:=T[i];
end;
close(fo);
END.
Cách 2: Duyệt từ đầu dãy về cuối dãy
Const Max = 5000;
Var a,L,T:array [0..Max] of integer;
i,j,n,jmax:integer; fi,fo:text;
Procedure Nhapdulieu;
begin
assign(fi,'day.inp'); reset(fi); N:=0;
while not eof (fi) do
begin
N:=N+1; read(fi,a[N]);
end;
close(fi);
end;
Procedure quyhoachdong;
Begin
L[0]:=1;a[0]:=low(integer);a[N+1]:=high(integer);
for i:=1 to N+1 do
begin
jmax:=0;
for j:=0 to i-1 do
if (a[j]<a[i]) and (L[j]>L[jmax]) then jmax:=j;
L[i]:=L[jmax]+1;
T[i]:=jmax;
end;
End;
Procedure Truyvet(i:integer); {dùng đệ quy để in dãy tối ưu}
Begin
i:=T[i];
if i=0 then exit;
truyvet(i);
write(fo,a[i],' ');
end;
Procedure ghidulieu;
Begin
assign(fo,'day.out'); rewrite(fo);
quyhoachdong;
writeln(fo,'so luong phan tu=',l[n+1]-2);
truyvet(N+1);
close(fo);
End;
BEGIN
Nhapdulieu;
Ghidulieu;
END.
Bài toán 2: Mê cung
Trong một chuyến thám hiểm mạo hiểm, một đoàn thám hiểm không may lọt vào một mê cung với nhiều cạm bẫy. Trong mê cung đó chỉ có một lối ra duy nhất, lối ra bao gồm các ô hình vuông được xếp thành một hàng dài. Muốn đi được ra ngoài mọi người phải bước qua một hàng các ô hình vuông đó và phải bước theo quy tắc sau:
- Quy tắc 1: Mỗi bước chỉ có thể bước một ô, hai ô hoặc ba ô
- Quy tắc 2: Từ người thứ 2 trở đi bước theo quy tắc 1 và không được trùng với các cách bước của tất cả những người đi trước đó.
Hỏi đoàn thám hiểm đó còn lại tối thiểu bao nhiêu người không thể thoát ra khỏi mê cung đó.
Dữ liệu vào: mecung.inp
- Dòng 1: ghi số nguyên m (m<=1018) là số người trong đoàn thám hiểm
- Dòng 2: ghi một số nguyên n (n<=70) là tổng số ô vuông
Dữ liệu ra: mecung.out
Gồm một số nguyên duy nhất thể hiện số người còn lại tối thiểu bao nhiêu người không thể thoát ra khỏi mê cung
Ví dụ:
Bài toán 3: Dãy con chung dài nhất
Var a,L,T:array [0..Max] of integer;
i,j,n,jmax:integer; fi,fo:text;
Procedure Nhapdulieu;
begin
assign(fi,'day.inp'); reset(fi); N:=0;
while not eof (fi) do
begin
N:=N+1; read(fi,a[N]);
end;
close(fi);
end;
Procedure quyhoachdong;
Begin
L[0]:=1;a[0]:=low(integer);a[N+1]:=high(integer);
for i:=1 to N+1 do
begin
jmax:=0;
for j:=0 to i-1 do
if (a[j]<a[i]) and (L[j]>L[jmax]) then jmax:=j;
L[i]:=L[jmax]+1;
T[i]:=jmax;
end;
End;
Procedure Truyvet(i:integer); {dùng đệ quy để in dãy tối ưu}
Begin
i:=T[i];
if i=0 then exit;
truyvet(i);
write(fo,a[i],' ');
end;
Procedure ghidulieu;
Begin
assign(fo,'day.out'); rewrite(fo);
quyhoachdong;
writeln(fo,'so luong phan tu=',l[n+1]-2);
truyvet(N+1);
close(fo);
End;
BEGIN
Nhapdulieu;
Ghidulieu;
END.
Bài toán 2: Mê cung
Trong một chuyến thám hiểm mạo hiểm, một đoàn thám hiểm không may lọt vào một mê cung với nhiều cạm bẫy. Trong mê cung đó chỉ có một lối ra duy nhất, lối ra bao gồm các ô hình vuông được xếp thành một hàng dài. Muốn đi được ra ngoài mọi người phải bước qua một hàng các ô hình vuông đó và phải bước theo quy tắc sau:
- Quy tắc 1: Mỗi bước chỉ có thể bước một ô, hai ô hoặc ba ô
- Quy tắc 2: Từ người thứ 2 trở đi bước theo quy tắc 1 và không được trùng với các cách bước của tất cả những người đi trước đó.
Hỏi đoàn thám hiểm đó còn lại tối thiểu bao nhiêu người không thể thoát ra khỏi mê cung đó.
Dữ liệu vào: mecung.inp
- Dòng 1: ghi số nguyên m (m<=1018) là số người trong đoàn thám hiểm
- Dòng 2: ghi một số nguyên n (n<=70) là tổng số ô vuông
Dữ liệu ra: mecung.out
Gồm một số nguyên duy nhất thể hiện số người còn lại tối thiểu bao nhiêu người không thể thoát ra khỏi mê cung
Ví dụ:
mecung.inp
|
mecung.out
|
20
5
|
7
|
Bài toán 3: Dãy con chung dài nhất
Cho 2 dãy số nguyên A=<a1,a2,..,an>
và B=<b1,b2,…,bm>. Hãy tìm dãy số nguyên
C sao cho C là dãy con chung dài nhất của A và B.
Dữ liệu vào: từ tệp daychung.inp gồm 3 dòng
-
Dòng 1 ghi 2 số nguyên n,m là độ dài 2 dãy
-
Dòng 2 ghi n số nguyên cách nhau bởi dấu cách
-
Dòng 3 ghi m số nguyên cách nhau bởi dấu cách
Dữ liệu ra: Ghi vào tệp daychung.out gồm 2 dòng
-
Dòng 1 ghi 1 số nguyên thể hiện độ dài xâu cong chung
dài nhất
-
Dòng 2 ghi các phần tử của xâu con chung, mỗi phần tử
cách nhau bởi dấu cách.
v Ví dụ:
v Ví dụ:
daychung.inp
|
daychung.out
|
6 6
1 5 7 8 9 6
1 2 3 7 9 6
|
4
1 7 9 6
|
Bài toán 4: Xâu con chung dài nhất (như bài trên)
Xâu
kí tự A được gọi là xâu con của xâu kí tự B nếu ta có thể xóa đi một số kí tự
trong xâu B để được xâu A.
Cho 2 xâu ký tự X,Y. Hãy tìm xâu kí
tự Z có độ dài lớn nhất và là con của cả X và Y.
Input:
Dòng 1 chứa xâu X
Dòng 2 chứa xâu Y
Output:
chỉ gồm 1 dòng ghi độ dài xâu Z tìm được
Ví dụ:
Input.inp
|
Output.out
|
ALGORITHM
LOGARITHM
|
7
|
Bài toán 5: Ba lô (cái túi)
Cho n gói hàng (n<=1000). Gói hàng thứ i có khối lượng là W[i]<=1000
và giá trị V[i]<=1000. Cần chọn những gói hàng nào để bỏ vào một ba lô sao
cho tổng giá trị của các gói hàng đã chọn là lớn nhất nhưng tổng khối lượng của
chúng không vượt quá khối lượng M<=1000 cho trước. Mỗi gói chỉ chọn 1 hoặc
không chọn.
Input data: cho file văn bản balo.inp
- - Dòng 1: N, M cách nhau ít nhất 1 dấu
cách
- - N dòng tiếp theo: mỗi dòng gồm 2 số
Wi và Vi là khối lượng và giá trị gói hàng
Output data: ghi kết quả vào file văn bản
balo.out giá trị lớn nhất của các gói hàng mà balo có thể chứa.
Ví dụ:
balo.inp
|
balo.out
|
5 13
3 4
4 5
5 6
2 3
1 1
|
16
|
Giải thích
n = 5; M = 13
I
|
1
|
2
|
3
|
4
|
5
|
W[i]
|
3
|
4
|
5
|
2
|
1
|
V[i]
|
4
|
5
|
6
|
3
|
1
|
Tổng giá trị của các gói hàng bỏ
vào ba lô: 16
Các gói được chọn: 1(3, 4) 2(4,
5) 3(5, 6) 5(1, 1)
Cách giải:
Gọi f[i,j] là tổng giá trị lớn nhất của túi
khi xét từ vật 1 đến vật i với trọng lượng không vượt quá j (trọng lượng giới hạn).
Khi
xét vật i thì có 2 khả năng
- Khả năng 1:
nếu trọng lượng của vật i là w[i] lớn hơn trọng lượng giới hạn j (w[i]>j) thì
giá trị của vật i bằng giá trị của vật
i-1 tại giới hạn j.
Tức
là f[i,j]=f[i-1,j]
- Khả năng 2: nếu
trọng lượng vật i là w[i] nhỏ hơn hoặc bằng giới hạn j (w[i]<=j) thì
có thể bỏ được vật i vào túi, trọng lượng còn lại của túi là j-w[i]
có thể chọn từ các vật từ 1 đến i-1. {giải thích: túi chỉ chứa được trọng lượng j, khi đã bỏ vào túi trọng lượng w[i] thì trọng lượng còn lại của túi là j-w[i] được chọn từ các vật trước đó}. Vậy giá trị
của túi khi bỏ vật i vào là giá trị
của vật i-1 tại giới hạn j-w[i] cộng với giá trị của vật i là v[i].
Tức là f[i,j]=f[i-1,j-w[i]]+v[i]
Với 2 khả năng có thể xét ở trên thì ta lấy giá
trị của khả năng nào tối ưu nhất ?
Muốn biết
khả năng nào tối ưu thì ta xét xem giá trị của khả năng nào lớn hơn thì ta lấy
khả năng đó.
Tức là F[i,j]=max(f[i-1,j], f[i-1,j-w[i]]+v[i])
code QHĐ
f[0,j]:=0;
for i:=1 to n do
for j:=1 to m do
if w[i]<=j then
f[i,j]:=max(f[i-1,j],f[i-1,j-w[i]]+v[i])
else f[i,j]:=f[i-1,j];
write(fo,f[n,m]);
Bài toán 6: Farmer (người nông dân)
Một người có N mảnh đất và M dải
đất. Các mảnh đất có thể coi là một tứ giác và các dải đất thì coi như một đường
thẳng. Dọc theo các dải đất ông ta trồng các cây bách, dải đất thứ i có Ai cây
bách. Ông ta cũng trồng các cây bách trên viền của các mảnh đất, mảnh đất thứ j
có Bj cây bách. Cả ở trên các mảnh đất và dải đất, xen giữa 2 cây bách ông ta
trồng một cây ôliu. Ông ta cho con trai được chọn các mảnh đất và dải đất tuỳ ý
với điều kiện tổng số cây bách không vượt quá Q. Người con trai phải chọn thế
nào để có nhiều cây ôliu (loài cây mà anh ta thích) nhất.
Input data: dữ liệu được cho
trong file Famer.inp
Dòng đầu tiên bao gồm:
Đầu tiên
là số Q (0<=Q<=150000) là số cây bách mà người con được chọn; sau đó là số
nguyên M là số cánh đồng; tiếp theo là số nguyên K là số dải đất.
-
Dòng thứ hai chứa M số nguyên N1, N2,
…, Nm (3<= N1, N2, …, Nm<=150)
là số cây bách trên cánh đồng
-
Dòng thứ 3 chứa K số nguyên R1, R2,
…, Rk (2<= R1, R2, …, Rk <=
150) là số cây bách trên dải đất.
Output data: Ghi ra tệp Farmer.out gồm 1 số nguyên duy nhất thể
hiện số cây oliu lớn nhất mà người con có thể thừa hưởng.
Ví dụ
Famer.inp
|
Famer.out
|
17 3 3
13 4 8
4 8 6
|
17
|
Bài toán 7: Đổi tiền
Bạn được
cho một tập hợp các mệnh giá tiền. Tập hợp luôn chứa phần tử mang giá trị 1. Mỗi
mệnh giá có vô hạn các đồng tiền mang mệnh giá đó. Cho số tiền S, hãy tìm cách
đổi S thành ít đồng tiền nhất, sao cho mỗi đồng tiền có mệnh giá thuộc tập hợp
đã cho.
Input data: Dữ liệu vào được đọc
từ tệp doitien.inp gồm 2 dòng:
- Dòng 1:
Hai số nguyên dương N (số phần tử của tập hợp mệnh giá tiền) và S (số tiền cần
đổi) (1 ≤ N ≤ 100; 1 ≤ S ≤ 106 ).
- Dòng 2: N
số nguyên dương biểu thị mệnh giá của các phần tử trong tập hợp (giá trị không
vượt quá 100).
Output data: Ghi kết quả ra tệp doitien.out gồm một số nguyên duy nhất
là số đồng tiền ít nhất có thể đổi được.
Ví dụ
doitien.inp
|
doitien.out
|
2 3
1 2
|
2
|
Bài toán 8: Bố trí phòng họp
Có n cuộc họp, cuộc họp thứ i bắt đầu vào
thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội thảo nên 2
cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của
chúng không giao nhau hoặc chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để
phục vụ được nhiều cuộc họp nhất.
Input data: file văn
bản phonghop.inp
-
Dòng
1: số nguyên dương N (N<=1000)
-
N
dòng tiếp theo: dòng thứ i chứa 2 số nguyên dương (ai,bi<=1000) chỉ thời điểm
bắt đầu và thời điểm kết thúc của cuộc họp i
Output
data: file văn bản phonghop.out.
Một số nguyên duy nhất thể hiện số cuộc họp nhiều nhất
Ví dụ:
phonghop.inp
|
phonghop.out
|
4
4 5
5 6
1 6
6 9
|
3
|
Bài toán 9: Cho thuê máy
Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của N khách
hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ai đến bi và trả tiền thuê là ci.
Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng
máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ
có một máy cho thuê)
Input data: file văn bản thuemay.inp
-
Dòng
1: số nguyên dương N (N<=10000)
-
N
dòng tiếp theo: dòng thứ i chứa 3 số nguyên dương (ai,bi,ci<=100
Output
data: file văn bản
thuemay.out. Một số nguyên duy nhất thể hiện số tiền lớn nhất thu được.
Ví dụ:
thuemay.inp
|
thuemay.out
|
3
1 8 16
2 7 6
7 9 9
|
16
|
Bài toán 10: Tiền khách sạn
Trong dịp nghi lễ 30 tháng 4 và 1 tháng 5 vừa qua do
cùng đợt nghỉ với ngày giỗ tổ Hùng Vương 10 tháng 3(âm lịch) nên số ngày nghỉ
lễ tăng lên. Vì thế lượng khách du lịch đổ về Nha Trang tham quan cũng tăng kỷ
lục, dẫn đến tinh trạng các khách sạn ở đây “cháy phòng”. Khách sạn Quang Huy
chỉ còn một phòng nên quyết định cho thuê phòng này theo hình thức thỏa thuận
về giá cả. Sau khi tổng hợp các đơn đặt hàng, khách sạn nhận được n đơn đặt
hàng, trong đó đơn đặt hàng thứ i đăng ký ngày bắt đầu là ai, ngày trả phòng là bi
và chấp nhận trả số tiền thuê phòng là ci.
Do có nhiều đơn đặt hàng, thời gian đặt phòng lại
chồng chéo nhau, số tiền khách hàng chấp nhận trả cho khách sạn cũng khác nhau
nên ban quản lý khách sạn đang rất khó khăn không biết nhận lời hay từ chối
khách hàng nào.
Yêu cầu: Viết chương trình
giúp khách sạn nhận đơn đặt phòng sao cho lợi nhuận thu được là lớn nhất.
Lưu ý: Theo điều lệ của
khách sạn, khách hàng phải trả phòng trước 12 giờ trưa, khách hàng khác có thể
nhận phòng từ 12 giờ trong một ngày.
Dữ liệu vào: được ghi trên tệp tienks.inp bao gồm:
o Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 12000) thể
hiện số đơn đặt hàng.
o n dòng tiếp theo gồm 3 số nguyên ai, bi và ci. Mỗi
số cách nhau một khoảng trắng với ràng buộc(l ≤ai ≤ bi ≤ 100, 0 ≤ c ≤1000).
Dữ liệu ra: lưu trong tệp tienks.out với một số nguyên thể hiện
số tiền lớn nhất
TIENKS.INP
|
TIENKS.OUT
| |
Vi dụ 1
|
3
128
236
476
|
20
|
Vi dụ 2
|
4
145
138
354
469
|
17
|
Bài liên quan
Comments[ 0 ]
Đăng nhận xét