Cắm hoa



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  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 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 ksố 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 liu t tp HOA.INP vào các biến k, nv[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 hng 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. Lp h thc: Gi T(i, j) là tổng giá tr thm mĩ khi gii bài toán vi i bó hoa mã s 1..ij l mã s 1..j, tc là độ thm mĩ thu được khi cm hết i bó hoa đầu tiên vào j l đầu tiên, ta thy:
a)      Nếu s bó hoa nhiu hơn s l, i > j thì không có cách cm 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 bng s l (i = j) thì ch có mt cách cm là bó nào vào l đó.
c)      Ta xét trường hp s bó hoa ít hơn hn s l (i < j). Có hai tình hung: l cui cùng, tc l th j được chn cho phương án ti ưu và l th j không được chn.
-          Nếu l cuối cùng, lọ th j được chn để cm bó hoa (cuối cùng) i thì i -1 bó hoa đầu tiên s được phân phi vào j - 1 l đầu tiên. Tổng giá tr thm mĩ s khi đó s  T(i - 1, j - 1) + v[i, j].
-          Nếu l th j không được chn cho phương án ti ưu thì ibó hoa phi được cm vào j-1 l đầu tiên và do đó tổng giá tr thm mĩ s là T(i, j-1).
Tng hp li ta có giá tr ti ưu khi cm 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 chc d liu và chương trình: Nếu dùng mng hai chiu T thì ta có th tính như trong bng 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[i1] 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[i1] 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í ca bit jtrong 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;
Vi j = 0, tc là khi không có l nào và không có bó hoa nào ta khi tr:
fillchar(L[0],16,0);
T[0] := 0;
Vi mi j = 1..n, ta lưu ý s bó hoa phi không ln hơn s l, tc là ij. Vi i = jta s cm mi bó vào mt l. Để thc hin điu này ta lưu ý rng phn t L[j-1] ti bước trước đã cho biết j -1 l đều có hoa do đó ta ch cn đánh du l th j cho bước j:
L[j] := L[j-1];
batbit(j,j);
Như vy ta cn chia quá trình duyt theo các l hoa t 1..n thành hai giai đon.
Giai đon 1: Duyt t l 1 đến l k, trong đó k chính là s bó hoa và theo đầu bài,
                                 k £ n.
Giai đon 2: Duyt nt n - kl hoa còn li.
Phương án quy hoch động vi mng mt chiu 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à mt cách phát biu khác ca bài toán cm hoa:
Bài toán
Câu lc b - Hc sinh gii Tin học, Hà Ni, năm 2000
Cn b trí k nhóm hc sinh vào k trong s n phòng hc chuyên đề sao cho nhóm có s hiu nh được xếp vào phòng có s hiu nh hơn phòng cha nhóm có s hiu ln. Vi mi phòng có nhn hc sinh, các ghế tha phi được chuyn ra hết, nếu thiếu ghế thì phi ly t kho vào cho đủ mi hc sinh mt ghế. Biết s hc sinh trong mi nhóm và s ghế trong mi phòng. Hãy chn phương án b trí sao cho tng s ln chuyn ghế ra và chuyn ghế vào là ít nht.
 

Không có nhận xét nào:

Đăng nhận xét