Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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ỡ MN2thao tác.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts