Cho một bảng chia lưới ô vuông N dòng mã số 1..N tính từ trên
xuống và M cột mã số 1..M tính từ trái
sang. Mỗi ô được phép đặt không quá 1 viên sỏi. Người ta cho trước giới hạn
tổng số sỏi được phép đặt trên dòng i là di, i = 1..N và trên mỗi
cột j là Cj, j = 1..M. Hãy tìm một phương án xếp được nhiều sỏi nhất
trong bảng, biết rằng các dữ liệu đều hợp lệ và bài toán luôn có nghiệm.
Thuật toán
Tổ chức dữ liệu:
const MN = 101;
d: array[0..MN] of integer;
c: array[0..MN] of integer;
a: array[1..MN,1..MN] of byte;
trong đó d là mảng chứa giới hạn sỏi trên dòng, c - trên
cột, a là mảng hai chiều biểu diễn bảng chia lưới ô vuông, a[i,j] = 1 - có viên
sỏi đặt tại dòng i, cột j; a[i,j] = 0 - không có sỏi tại ô này. Ta thực hiện kỹ
thuật hai pha như sau.
procedure XepSoi;
var j: integer;
begin
fillchar(a,sizeof(a),0);
d[0] := M+1; { dat linh
canh }
{ Pha 1 } XepDong;
{ Pha 2 } for j := 1 to
M do ChinhCot(j);
end;
Pha thứ nhất: Xếp tối đa sỏi vào mỗi dòng. Mỗi dòng i ta xếp
liền nhau d[i] viên sỏi. Đồng thời ta sử dụng lại các biến mảng d và c với ý
nghĩa sau đây: d[i] cho biết vị trí cột của viên sỏi cuối cùng trên dòng i.
c[j] cho biết số sỏi còn có thể xếp thêm trên cột j. Dĩ nhiên, ta phải chỉnh
lại các giá trị c[j] mỗi khi xếp thêm 1 viên sỏi vào cột này. Nếu c[j] < 0
tức là ta cần bớt sỏi ở cột j. Thủ tục xếp dòng khi đó sẽ như sau.
procedure XepDong;
var i,j: integer;
begin
for i := 1 to N do
for j := 1 to d[i] do
begin
a[i,j] := 1;
dec(c[j]);
end;
end;
Pha thứ hai: Sau
khi xếp xong N dòng ta tiến hành chỉnh từng cột j có giá trị c[j] < 0 đến khi nào c[j] = 0. Để chỉnh cột j theo
phương pháp tham lam ta duyệt để chọn một dòng imin có chứa sỏi tại cột j và
đầu phải d[imin] đạt giá trị nhỏ nhất. Sau đó ta chuyển viên sỏi trên dòng imin
từ cột j sang cột d[imin]+1 và chỉnh lại các giá trị c[j] và d[imin]. Để tìm dòng imin ta cần dùng phần tử d[0] với
giá trị lớn nhất làm phần tử khởi đầu. Ta có thể cho giá trị này là M+1, vì mỗi
dòng không thể có qúa M viên sỏi. Bạn
cần lưu ý rằng khi d[imin] = M tức là mọi viên sỏi cuối cùng trên mỗi dòng đều
chiếm vị trí tại cột M tức là hết chỗ để đặt sỏi.
procedure ChinhCot(j: integer);
begin
while c[j] < 0 do
GiamCot(j);
end;
procedure GiamCot(j: integer);
var i: integer;
begin
i := DongMin(j);
a[i,j] := 0; { Bo vien
soi } inc(c[j]);
if d[i] = M then exit;
inc(d[i]); a[i,d[i]] :=
1; { Dat 1 vien vao day }
dec(c[d[i]]);
end;
function DongMin(j: integer): integer;
var i,imin: integer;
begin
imin := 0;
for i:=1 to N do
if a[i,j]=1 then
if d[i] < d[imin]
then imin := i;
DongMin := imin;
end;
Thí dụ dưới đây minh họa thuật toán với N = M = 4; d = (3,2,1,2), c = (2,2,2,2).
|
0
|
0
|
0
|
0
|
3
|
|
1
|
1
|
1
|
0
|
3
|
||||||||||||||||||||||||
|
0
|
0
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
||||||||||||||||||||||||
|
0
|
0
|
0
|
0
|
1
|
|
1
|
0
|
0
|
0
|
1
|
||||||||||||||||||||||||
|
0
|
0
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
||||||||||||||||||||||||
|
2
|
2
|
2
|
2
|
|
|
-2
|
-1
|
1
|
2
|
|
||||||||||||||||||||||||
|
Cấu
hình ban đầu
|
|
|
Sau
Pha 1
|
|
||||||||||||||||||||||||||||||
|
1
|
1
|
1
|
0
|
3
|
|
1
|
1
|
1
|
0
|
3
|
|
1
|
1
|
1
|
0
|
3
|
||||||||||||||||||
|
1
|
1
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
|
0
|
1
|
1
|
0
|
3
|
||||||||||||||||||
|
1
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
0
|
2
|
|
0
|
1
|
0
|
0
|
2
|
||||||||||||||||||
|
1
|
1
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
||||||||||||||||||
|
-2
|
-1
|
1
|
2
|
|
|
-1
|
-2
|
1
|
2
|
|
|
0
|
-2
|
0
|
2
|
|
||||||||||||||||||
|
Chỉnh cột 1
|
||||||||||||||||||||||||||||||||||
|
1
|
1
|
1
|
0
|
3
|
|
1
|
1
|
1
|
0
|
3
|
|
1
|
1
|
1
|
0
|
3
|
||||||||||||||||||
|
0
|
1
|
1
|
0
|
3
|
|
0
|
1
|
1
|
0
|
3
|
|
0
|
1
|
1
|
0
|
3
|
||||||||||||||||||
|
0
|
1
|
0
|
0
|
2
|
|
0
|
0
|
1
|
0
|
3
|
|
0
|
0
|
1
|
0
|
3
|
||||||||||||||||||
|
1
|
1
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
2
|
|
1
|
0
|
1
|
0
|
3
|
||||||||||||||||||
|
0
|
-2
|
0
|
2
|
|
|
0
|
-1
|
-1
|
2
|
|
|
0
|
0
|
-2
|
2
|
|
||||||||||||||||||
|
Chỉnh cột 2
|
||||||||||||||||||||||||||||||||||
|
1
|
1
|
1
|
0
|
3
|
|
1
|
1
|
0
|
1
|
4
|
|
1
|
1
|
0
|
1
|
4
|
||||||||||||||||||
|
0
|
1
|
1
|
0
|
3
|
|
0
|
1
|
1
|
0
|
3
|
|
0
|
1
|
0
|
1
|
4
|
||||||||||||||||||
|
0
|
0
|
1
|
0
|
3
|
|
0
|
0
|
1
|
0
|
3
|
|
0
|
0
|
1
|
0
|
3
|
||||||||||||||||||
|
1
|
0
|
1
|
0
|
3
|
|
1
|
0
|
1
|
0
|
3
|
|
1
|
0
|
1
|
0
|
3
|
||||||||||||||||||
|
0
|
0
|
-2
|
2
|
|
|
0
|
0
|
-1
|
1
|
|
|
0
|
0
|
0
|
0
|
|
||||||||||||||||||
|
Chỉnh cột 3
|
||||||||||||||||||||||||||||||||||
Độ phức tạp
Ta cần chỉnh M
cột. Mỗi cột ta cần lặp tối đa N lần, mỗi lần giảm được 1 viên sỏi trong cột.
Để giảm 1 viên sỏi này ta phải duyệt N dòng để tìm imin. Tổng cộng ta cần cỡ MN2
thao tác.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét