Olympic Quốc tế năm 1999.
Cần cắm hết k bó hoa khác nhau vào n lọ xếp
thẳng hàng sao cho bó hoa có số hiệu nhỏ được đặt trước bó hoa có số hiệu lớn.
Với mỗi bó hoa i ta biết giá trị thẩm mĩ khi cắm bó hoa đó vào lọ j là v[i, j].
Yêu
cầu: Xác định một phương án cắm hoa sao cho tổng giá trị thẩm mĩ là lớn nhất.
Dữ liệu vào ghi trong tệp văn bản HOA.INP:
-
Dòng đầu tiên là hai trị k và n.
-
Từ dòng thứ hai trở đi là các giá trị v[i,
j] trong khoảng 0..10, với i = 1..k và j = 1..n; 1 £ k £ n £ 100.
Dữ liệu ra ghi trong tệp văn bản HOA.OUT: dòng đầu tiên là tổng giá trị thẩm mĩ của phương án cắm
hoa tối ưu. Từ dòng thứ hai là dãy k
số hiệu lọ được chọn cho mỗi bó hoa.
Các số liệu vào và ra đều là số tự nhiên và được ghi cách
nhau bởi dấu cách trên mỗi dòng.
Thí dụ:
HOA.INP
|
HOA.OUT
|
4 6
1
1 6 4 3
10
9
1 4 7
2 7
7
2 6 10 2 3
6 10
7 1 3 9
|
24
1 3 4 6
|
Kết quả cho
biết tổng giá trị thẩm mĩ sẽ đạt là 24 (điểm) nếu cắm hoa như sau:
-
Bó hoa 1 cắm vào lọ 1;
-
Bó hoa 2 cắm vào lọ 3;
-
Bó hoa 3 cắm vào lọ 4;
-
Bó hoa 4 cắm vào lọ 6.
Bài giải
Trước hết ta đọc dữ liệu từ tệp HOA.INP vào các biến k, n và v[i,
j].
(*-----------------------------------
Doc du
lieu
----------------------------------*)
procedure
doc;
var i,j:byte;
begin
assign(f,fn);
reset(f);
readln
(f,k,n);
for i := 1 to
k do
for j := 1 to
n do
read(f,v[i,j]);
close(f);
end;
Các hằng và biến được khai báo như sau:
const
fn = 'hoa.inp'; {File du lieu vao }
gn = 'hoa.out'; {File du lieu ra }
mn = 101; {So luong toi da cac lo hoa: 100 }
bl = #32; {Dau
cach }
nl =
#13#10; {Xuong dong }
kk =
(mn+7) div 8; {So bit danh dau cac lo hoa }
type
mb1 =
array[0..mn] of byte; {mang byte 1 chieu }
mb2 =
array[0..mn] of mb1; {mang byte 2 chieu }
ml1 =
array[0..kk] of byte;
ml2 =
array[0..mn] of ml1;
mi1 =
array[0..mn] of integer;
var
n,k:
byte; {n - so luong lo, k - so luong bo hoa }
v: mb2;
{v[i,j]
- do tham my khi cam bo hoa i vao lo j }
L: ml2;
{cac mang danh dau
lo hoa
bit(i) = 1: lo hoa duoc chon
bit(i) = 0: lo hoa roi}
T: mi1; {T[i,j]: tong so do tham mi
khi cam i bo hoa vao day j lo
}
f,g: text; {files input va output }
1.
Lập hệ thức: Gọi T(i, j) là tổng giá trị thẩm mĩ khi giải bài toán với i bó hoa mã số 1..i và j lọ mã số 1..j, tức là độ thẩm mĩ thu được khi cắm hết i bó hoa đầu tiên vào j lọ đầu tiên, ta thấy:
a) Nếu số bó
hoa nhiều hơn số lọ, i > j thì không có cách cắm nào vì đầu bài yêu cầu phải cắm hết các bó hoa, mỗi
bó vào đúng 1 lọ.
T(i, j) = 0
b)
Nếu số bó hoa bằng số lọ (i = j) thì chỉ có một cách
cắm là bó nào vào lọ đó.
c)
Ta xét trường hợp số bó hoa ít hơn hẳn số lọ (i < j). Có hai tình huống: lọ cuối cùng, tức lọ thứ j được chọn cho phương án
tối ưu và lọ thứ j không được chọn.
-
Nếu lọ cuối cùng, lọ thứ j được chọn để cắm bó hoa (cuối cùng) i thì i -1 bó hoa đầu tiên sẽ được phân phối vào j - 1 lọ đầu tiên. Tổng giá trị thẩm mĩ s
khi đó sẽ là T(i - 1, j - 1) + v[i,
j].
-
Nếu lọ thứ j không được chọn cho phương
án tối ưu thì i
bó hoa phải được cắm vào j-1
lọ đầu tiên và do đó tổng giá trị thẩm mĩ sẽ là
T(i, j-1).
Tổng hợp lại ta có giá trị tối ưu khi cắm i bó hoa vào j lọ là:
T(i,j) = max
{T(i-1,j-1)+v[i,j],T(i,j-1)}
2. Tổ chức dữ liệu và
chương trình: Nếu dùng mảng hai chiều T thì ta có thể tính như trong bảng dưới đây:
|
…
|
j – 1
|
j
|
|
…
|
…
|
…
|
|
|
i–1
|
…
|
[i-1,j-1]
|
|
|
i
|
…
|
[i,j-1]
|
[i,j]?
|
|
…
|
…
|
…
|
|
|
T(i,j) = max {T(i-1,j-1) +
v[i,j],T(i,j-1)}
|
Ngoài ra, ta còn cần đặt trong mỗi ô của bảng trên một mảng dữ liệu bao
gồm n phần tử để đánh dấu lọ hoa nào
được chọn cho mỗi tình huống. Gọi mảng dữ liệu đó là L[i, j], ta dễ thấy là nên
điền bảng lần lượt theo từng cột, tại mỗi cột ta điền bảng từ dưới lên theo
luật sau:
-
Nếu T[i-1, j-1] + v[i, j]
> T[i, j-1] thì ta phải thực hiện hai thao tác:
o
Đặt lại trị T[i, j]:= T[i-1, j-1] + v[i, j].
o
Ghi nhận việc chọn lọ hoa j
trong phương án mới, cụ thể lấy phương án cắm hoa (i-1, j-1) rồi bổ sung thêm
thông tin chọn lọ hoa j như sau: đặt L[i,
j]:= L[i-1, j-1] và đánh dấu phần tử j trong
mảng L[i, j].
-
Nếu T[i-1, j-1] + v[i,
j] ≤ T[i, j-1] thì ta sẽ không
chọn lọ j để cắm bó hoa i và do đó chỉ cần copy L[i,
j-1] sang L[i, j],
tức là ta bảo lưu phương án (i, j-1).
3. Làm tốt. Phương án dùng mảng hai chiều tốn kém về miền nhớ. Ta có thể
dùng một mảng một chiều T[0..100] xem
như một cột của bảng T nói trên. Ta
duyệt j bước. Tại bước thứ j, giá trị T[i] sẽ là trị tối ưu khi
cắm hết i bó hoa vào j lọ. Như vậy, tại bước thứ j ta có:
-
Nếu T[i–1] tại bước j -1 + v[i,
j] > T[i] tại bước j - 1 thì ta phải thực hiện hai thao tác:
o Đặt lại trị T[i]
tại bước j:= T[i–1] tại bước j -1 + v[i, j].
o
Ghi nhận việc chọn lọ hoa j trong phương án mới, cụ thể lấy
phương án cắm hoa (i-1) ở bước j - 1 rồi bổ sung thêm thông tin
chọn lọ hoa j như sau: đặt
L[i] tại bước j:= L[i -
1] tại
bước j - 1
và đánh dấu phần tử j trong mảng L[i].
-
Nếu T[i -
1] tại
bước j - 1
+ v[i, j] ≤ T[i]
tại bước j - 1 thì ta không phải làm gì vì sẽ bảo lưu phương án cũ.
Biểu thức so
sánh cho biết khi cập nhật mảng T từ
bước thứ j - 1 qua bước thứ j ta phải tính từ dưới lên, nghĩa là
tính dần theo chiều giảm của i:= j..1.
Để đánh dấu các lọ hoa ta dùng mảng L[0..MN]
mỗi phần tử L[i] lại là một dãy s byte.
Nếu dùng một bit cho mỗi lọ hoa thì số byte cần dùng để đánh dấu tối đa MN lọ hoa phải là:
kk = (MN+7)
div 8
Với MN = 101 ta tính được
kk = (101+7)
div 8 = 13
Khi cần đánh dấu lọ hoa thứ j trong dãy L[i] ta bật bit thứ j trong L[i]. Khi cần xem lọ thứ j có được chọn hay không ta gọi hàm GetBit để lấy trị (0 hoặc 1) của bit j trong dãy bit L[i].
Ta chú ý tới hai biểu thức sau:
-
Để xác định byte thứ
mấy trong dãy chứa bit j ta tính:
b := j div 8;
-
Để xác định vị trí của bit j
trong byte thứ b ta tính:
p := j mod 8;
(*
------------------------------------------
Cho gia tri bit thu j trong day byte L[i]
-------------------------------------------*)
function
getbit(i,j: byte):byte;
var b,p: byte;
begin
b := j div 8;
p := j mod 8;
getbit := (L[i][b]
shr p) and 1;
end;
(*
----------------------------------------
Gan tri 1 cho
bit j trong day byte L[i]
---------------------------------------*)
procedure
batbit(i,j:byte);
var b,p: byte;
begin
b := j shr 3;
p := j and 7;
L[i][b] := L[i][b] or (1 shl p);
end;
Với j = 0, tức là khi không có lọ nào và
không có bó hoa nào ta khởi trị:
fillchar(L[0],16,0);
T[0] := 0;
Với mỗi j = 1..n, ta lưu ý số bó hoa phải không lớn hơn số lọ, tức là i ≤ j. Với i = j
ta sẽ cắm mỗi bó
vào một lọ. Để thực hiện điều này ta lưu ý rằng phần tử L[j
-1] tại bước trước đã cho biết j -1 lọ đều có hoa do đó ta chỉ cần đánh dấu lọ thứ j cho bước j:
L[j] := L[j-1];
batbit(j,j);
Như vậy ta cần chia
quá trình duyệt theo các lọ hoa từ 1..n thành hai giai đoạn.
Giai đoạn 1:
Duyệt từ lọ 1 đến lọ k, trong
đó k chính là số bó hoa và theo đầu bài,
k £ n.
k £ n.
Giai đoạn 2: Duyệt nốt n - k
lọ hoa còn lại.
Phương án quy hoạch động với mảng một chiều khi đó sẽ như sau:
(*------------------------
Quy hoach dong
------------------------*)
procedure
xuly;
var i,j: byte;
begin
{1. Khoi tri }
fillchar(L,sizeof(L),0);
{danh dau cac
lo hoa duoc chon }
T[0] := 0; {do
tham mi }
{Vi co k bo hoa nen xet k lo dau tien }
for j := 1 to
k do
begin
L[j] := L[j-1];
batbit(j,j);
T[j] := T[j-1]+v[j,j];
for i := j-1 downto 1 do
if T[i] < T[i-1]+v[i,j] then
begin
T[i] := T[i-1]+v[i,j];
L[i] := L[i-1];
batbit(i,j);
end;
end;
{xet cac lo
con lai }
for j := k+1
to n do
for i := k downto 1 do
if T[i] <
T[i-1]+v[i,j] then
begin
T[i] := T[i-1]+v[i,j];
L[i] := L[i-1];
batbit(i,j);
end;
end;
(* Pascal *)
(*==================================
Hoa.pas: Quy hoach dong
===================================*)
uses crt ;
const
fn = 'hoa.inp'; {File du lieu vao }
gn = 'hoa.out'; {File du lieu ra }
mn = 101; {So luong toi da cac lo hoa: 100 }
bl = #32; {Dau
cach }
nl =
#13#10; {Xuong dong }
kk =
(mn+7) div 8; {So bit danh dau cac lo hoa }
type
mb1 = array[0..mn] of byte; {mang byte 1 chieu
}
mb2 =
array[0..mn] of mb1; {mang byte 2 chieu }
ml1 =
array[0..kk] of byte;
ml2 =
array[0..mn] of ml1;
mi1 =
array[0..mn] of integer;
var
n,k:
byte; {n - so luong lo, k - so luong bo hoa }
v: mb2;
{v[i,j]
- do tham my khi cam bo hoa i vao lo j }
L: ml2;
{cac mang danh dau lo hoa
bit(i) = 1: lo hoa duoc chon
bit(i) = 0: lo hoa roi }
T: mi1;
{T[i,j] tong do tham my khi cam i bo hoa vao
day j lo }
f,g: text; {files input va output }
(*-----------------------------------
Doc du lieu
----------------------------------*)
procedure doc; tự viết
(*
-----------------------------------------
Cho gia tri
bit thu j trong day byte L[i]
-------------------------------------------*)
function
getbit(i,j: byte):byte; tự viết
(*
----------------------------------------
Gan tri 1 cho
bit j trong day byte L[i]
-------------------------------------------*)
procedure batbit(i,j:byte); tự viết
(*------------------------
Quy hoach dong
------------------------*)
procedure
xuly; tự viết
(*--------------------------------
Ghi ket qua T[k] -
Tong do tham mi cac lo duoc chon
----------------------------------*)
procedure ghi; tự viết
BEGIN
doc; xuly; ghi;
END.
Bài toán sau đây là một cách phát biểu khác của bài toán cắm hoa:
Bài toán
Câu lạc bộ - Học sinh giỏi Tin học, Hà Nội, năm 2000
Cần bố trí k nhóm học sinh vào k trong số n phòng học chuyên đề sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ hơn phòng chứa nhóm có số hiệu lớn. Với mỗi phòng có nhận học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì phải lấy từ kho vào cho đủ mỗi học sinh một ghế. Biết số học sinh trong mỗi nhóm và số ghế trong mỗi phòng. Hãy chọn phương án bố trí sao cho tổng số lần chuyển ghế ra và chuyển ghế vào là ít nhất.
Không có nhận xét nào:
Đăng nhận xét