Đề tài Bài toán đổi tiền (kỹ thuật quy hoạch động)

Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham ăn, quay lui,... Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong bài viết này, tôi muốn đề cập với các bạn một thuật toán khác, đó là thuật toán quy hoạch động. Ý tưởng cơ bản của thuật toán là: Để giải một bài toán ta chia bài toán đó thành các bài toán nhỏ hơn để giải một cách dễ dàng. Sau đó kết hợp lời giải các bài toán con, ta có được lời giải bài toán ban đầu. Trong quá trình giải các bài toán con đôi khi ta gặp rất nhiều kết quả trùng lặp của các bài toán con. Để tăng tính hiệu quả, thay vì phải tính lại các kết quả đó, ta lưu chúng vào một bảng. Khi cần lời giải của một bài toán con nào đó ta chỉ cần truy tìm trong bảng, không cần tính lại. Ý tưởng của thuật toán quy hoạch động khá đơn giản nhưng khi áp dụng thuật toán vào trường hợp cụ thể lại không dễ dàng (điều này cũng tương tự như nguyên tắc Dirichlet trong toán vậy). Khi giải bài toán bằng phương pháp này, chúng ta phải thực hiện hai yêu cầu quan trọng sau: - Tìm công thức truy hồi xác định nghiệm bài toán qua nghiệm các bài toán con nhỏ hơn. - Với mỗi bài toán cụ thể, ta đề ra phương án lưu trữ nghiệm một cách hợp lý để từ đó có thể truy tìm nhanh nhất. I. Phương Pháp Quy Hoạch Động 1. Phương pháp quy hoạch động Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ XX. Phương pháp này đã được áp dụng để giải hàng loạt bài toán thực tế trong: kỹ thuật công nghệ, tổ chức sản xuất, toán kinh tế…Nhưng cũng cần lưu ý rằng có một số bài toán mà cách giải bằng quy hoạch động tỏ ra không thích hợp. Trong cuộc sống, ta thường gặp một số bài toán tối ưu sau: Có một đại lượng F hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là giá trị của F phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ưu của F. Giá trị của F phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng được gọi là một trạng thái của hệ thống và phụ thuộc vào cách thức đạt được giá trị F trong từng giai đoạn mà mỗi cách tổ chức được gọi là một điều khiển. Đại lượng F thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của F được gọi là quá trình điều khiển tối ưu. Bellman phát biểu nguyên lý tối ưu (cũng gọi là nguyên lý Bellman) mà ý tưởng cơ bản là: “Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”. Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động. Thuật ngữ này nói lên quá trình điều khiển là động: có thể trong một số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng chung cả quá trình lại là tốt nhất. Khi giải bài toán bằng cách “chia để trị” chuyển việc giải bài toán kích thước lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì thuật toán này thường được thể hiện bằng các chương trình con đệ quy. Khi đó, trên thực tế, nhiều kết quả trung gian phải tính nhiều lần. Nói cách khác phương pháp quy hoạch động đã thể hiện sức mạnh của kỹ thuật chia để trị. Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dưới lên). Nó được bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giải nhất và giải được ngay). Bằng cách tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt tới kết quả của trường hợp có kích thước lớn dần lên và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của trường hợp tổng quát nhất. Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán A(n) phụ thuộc tham số n (có thể n là một véc tơ) mà A(n0)=A với n0 là trạng thái ban đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(n) với tham số n bằng cách áp dụng nguyên lý tối ưu của Bellman. Cuối cùng cho n=n0 sẽ nhận được kết quả của bài toán A ban đầu. 2. Các bước thực hiện quy hoạch động Bước 1: Lập hệ thức Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng phương trình truy toán (dạng hàm hoặc thủ tục đệ quy). Fk = Fk-1 + Gk (*) là phương trình truy toán Bước 2: Tổ chức dữ liệu và chương trình Tổ chức dữ liệu sao cho đạt các yêu cầu sau: Dữ liệu được tính toán dần theo các bước. Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại. Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập. Cụ thể Các giá trị của Fk thường được lưu trữ trong một bảng (mảng một chiều hoặc hai chiều). Lưu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải. Dựa vào công thức, phương trình truy toán (*) và các giá trị đã có trong bảng để tìm dần các giá trị còn lại của bảng. Ngoài ra, cần mảng lưu trữ nghiệm tương ứng với các giá trị tối ưu trong từng gian đoạn. Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu trong từng giai đoạn đã xây dựng, tìm ra kết quả bài toán. Bước 3: Làm tốt Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thước miền nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước. Trong một số trường hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0, 1 bởi mảng hai chiều mới bằng cách dùng kỹ thuật quản lý bit. 3. Các nguyên tắc cơ bản của quy hoạch động Quy hoạch động là việc quy hoạch từng giai đoạn của quá trình qua nhiều giai đoạn mà trong đó mỗi giai đoạn chỉ tối ưu hóa một bước.Tuy nhiên khi quy hoạch một quá trình nhiều giai đoạn, ở mỗi bước ta phải lựa chọn điều khiển trên cơ sở không phải xuất phát từ lợi ích nhỏ hẹp của chính bước đó mà từ lợi ích chung của toàn bộ quá trình (bài toán). - Nguyên tắc đánh số các giai đoạn từ dưới lên Đối với giai đoạn cuối có thể làm cho tốt nhất và không lo hậu quả, khi đó giai đoạn này trở nên ổn định và ta có thể xét giai đoạn ở trước đó và cứ tiếp tục cho tới lúc ta đi được tới giai đoạn đầu của quá trình. - Nguyên tắc thông số hóa bài toán Ở giai đoạn sát giai đoạn cuối cùng, ta chưa biết kết quả nên ta phải đặt giả thiết cho giai đoạn này rồi ứng với giả thiết đó ta tìm điều khiển tối ưu cho giai đoạn cuối cùng. Ở các bước khác tình hình cũng xãy ra như vậy, do đó quá trình điều khiển tối ưu sẽ phụ thuộc vào các thông số đặc trưng cho kết quả ở bước trước. - Nguyên tắc lồng Lồng bài toán ban đầu vào bài toán rộng hơn hay một họ các bài toán và do đó bài toán ban đầu là một trường hợp riêng của họ bài toán này, họ bài toán này nhờ có các thông số nên ta giải được. Ta sẽ thử kết quả của bài toán với các thông số khác nhau cho tới một lúc được thông số của bài toán ban đầu thì dừng lại. - Nguyên tắc tối ưu ( Bellman ) Có tính chất: dù trạng thái ban đầu và điều khiển ban đầu có dạng như thế nào thì điều khiển tiếp theo cũng là tối ưu đối với trạng thái thu được trong kết quả tác động những điều khiển ban đầu. 4. Hạn chế của quy hoạch động Việc tìm công thức, phương trình truy toán hoặc tìm cách phân rã bài toán nhiều khi đòi hỏi sự phân tích tổng hợp rất công phu,dễ sai sót, khó nhận ra như thế nào là thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời giải của các bài toán con cũng cho kết quả của bài toán lớn hơn. Không tìm được công thức truy hồi. Số lượng bài toán con cần giải quyết và lưu trữ kết quả có thể rất lớn không thể chấp nhận được. Khi bảng lưu trữ đòi hỏi mảng hai chiều, ba chiều … thì khó có thể xử lý dữ liệu với kích cỡ mỗi chiều lớn hàng trăm. Có khi những bài toán không thể giải được bằng quy hoạch động. 5. Phạm vi áp dụng: Các bài toán tối ưu: như tìm xâu con chung dài nhất, bài toán balô (1,2,3), tìm đường đi ngắn nhất, bài toán đổi tiền và một số phép biến đổi ít nhất... Các bài toán có công thức truy hồi. II.Các Bài Toán Về Quy Hoạch Động 1.Một số bài toán đơn giản: Bài toán 1: Cho hai dãy số nguyên (a1,a2,...,am), (b1,b2,...,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên (coi dãy không có số nguyên nào là dãy con của mọi dãy và có độ dài bằng 0). Lời giải Chúng ta có thể thấy ngay rằng độ phức tạp của bài toán trên phụ thuộc vào hai số m, n. Xét hai trường hợp: + Trường hợp 1:; m=0 hoặc n=0. Đây là trường hợp đặc biệt, có duy nhất một dãy con chung của hai dãy có độ dài bằng 0. Vì vậy dãy con chung có độ dài lớn nhất của chúng có độ dài bằng 0. + Trường hợp 2: m# 0 và n # 0. Trong trường hợp này, ta xét các bài toán nhỏ hơn là tìm dãy con chung có độ dài lớn nhất của hai dãy (a1,a2,...,ai), (b1,b2,...,bj) với 0 <= i <= m, 0 <= j <= n. Gọi [i,j] là độ dài l của dãy con chung lớn nhất của hai dãy (a1,...,ai), (b1,...,bj). Như vậy ta phải tính tất cả các l[i,j] trong đó 0<=i<=m, 0<=j<=n. Chúng ta có thể  thấy ngay rằng  l[0,0]=0. Giả sử ta tính được l[s,t] với 1         - Nếu ii # bj thì l[i,j]=max{l[i-1,j], l[i,j-1]}.         - Nếu ii=bj thì l[i,j]= 1+l[i-1,j-1]. Với những nhận xét trên, ta hoàn toàn tính được l[m,n] chính là độ dài dãy con chung dài nhất của (a1,..am), (b1,..bn). Để tìm phần tử của dãy con, ta xuất phát từ ô l[m,n] tới ô l[0,0]. Giả sử ta đang ở ô l[i,j]. Nếu ai=bj thì ta thêm ai vào dãy con rồi nhảy tới ô l[i-1,j-1]. Nếu aibj thì l[i,j]=l[i-1,j] hoặc l[i,j]=l[i,j-1]. Nếu l[i,j]=l[i-1,j] thì nhảy tới ô l[i-1,j], ngược lại thì nhảy tới ô l[i,j-1]. Sau đây là lời giải của bài toán. Chương trình được viết bằng ngôn ngữ Pascal: uses crt;  const fi='b2.inp';  var a:array[1..10] of integer; b:array[1..10] of integer; kq:array[0..10,0..10] of integer; i,j,maxa,maxb:integer; f:text;    procedure init;   begin  assign(f,fi); reset(f); i:=0;  while not(eoln(f)) do begin inc(i); read(f,a[i]); end; maxa:=i;  readln(f); i:=0;  while not(eoln(f)) do begin inc(i); read(f,b[i]); end; maxb:=i;  close(f);  end; function max(a,b:integer):integer;   begin  if a>b then max:=a else max:=b;  end;    begin  init;  kq[0,0]:=0;  for i:=1 to maxa do for j:=1 to maxb do if a[i]b[j] then kq[i,j]:=max(kq[i-1,j],kq[i,j-1]) else kq[i,j]:=kq[i-1,j-1]+1;  writeln('Do dai day con chung lon nhat:',kq[maxa,maxb]);  i:=maxa; j:=maxb;  while (i>0)or(j>0) do if a[i]=b[j] then begin write(a[i]); dec(i); dec(j); end else if kq[i-1,j]=kq[i,j] then dec(i) else dec(j);  end. Với nội dung file ‘b2.inp’ chứa 2 dãy (a1,a2,..am) ,(b1,b2,..bn) sau: 1 2 3 2 3 4 6 6 9 8 7 Bài toán 2: Cho cái túi chứa được trọng lượng tối đa là w. Có n đồ vật, đồ vật thứ i có khối lượng a[i] và giá trị c[i],  1<= i <=n. Tìm cách xếp đồ vật vào túi sao cho đạt giá trị lớn nhất. Lời giải  Gọi f(k,w) là giá trị lớn nhất của túi đựng trọng lượng w và chỉ chứa các đồ vật từ 1 đến k. Nếu k=1 thì f(k,w)=(w div a[1])*c[1].Giả sử tính được f(s,t) với 1<S< tính Can 1<t Đặt: tg=w div a[k], f(k,w)=max{f(k-1,u)+x*c[k]}  (*) ,với x=0,1,2,...,tg, u=w-x*a[k] Giá trị lớn nhất là f(n,w).Ta dùng mảng bảng ghi a[1..n,1..w] chứa kết quả trung gian. Mỗi bản ghi a[k,w] chứa giá trị f(k,w) và giá trị x thoả mãn công thức (*). Để xác định số lượng x[i] đồ vật I thoả mãn điều kiện tối ưu, ta xuất phát từ a[n,w] xác định được x[n]. Nhảy tới a[n-1,w-x[n]*a[n]] xác định được x[n-1]. Cứ như vậy tới x[1]. Uses crt;  const n=5; w=17; fi=’b3.inp’;  type kq=record num,val:integer; end;  var a:array[1..10] of integer; {khoi luong} c:array[1..10] of integer; {Gia tri} I,j,tg,k,max,save:integer; f:text; b:array[1..n,1..w] of kq;    procedure init;   begin  assign(f,fi); reset(f);  for i:=1 to n do begin read(f,a[i],c[i]); end;  close(f);  end;   begin  init;  for j:=1 to w do for i:=1 to n do begin tg:=j div a[i]; max:=0; for k:=0 to tg do if (b[i-1,j-k*a[i]].val+k*c[i])>max then begin max:=b[i-1,j-k*a[i]].val+k*c[i]; save:=k; end; b[I,j].val:=max; b[I,j].num:=save; end;  for i:=1 to n do begin  for j:=1 to w do write(b[I,j].val:3); writeln; end;  writeln(‘Max:’,b[n,w].val);  i:=n; j:=w;  while i>=1 do begin if b[I,j].num>0 then writeln(‘Co ‘,b[I,j].num,’ do vat ‘,i); j:=j-a[i]*b[I,j].num; dec(i); end;  readln;  end. Với nội dung file ‘b3.inp’ :hàng I chứa khối lượng a[i], giá trị c[i]: 3 4 4 5 7 10 8 11 9 13 Bài toán 3: Trò chơi Tán thủ Giả sử có hai tán thủ A, B cần đấu trực diện với nhau, qui định chung là người thắng trước n ván sẽ là người thắng cuộc (n = 4). Giả sử hai tán thủ A, B là ngang sức và do đó sác xuất thắng, thua trong mỗi ván là 50/50. Giả sử P(i,j) là sác xuất sao cho A cần thắng thêm i ván nữa , B cần thắng thêm j ván nữa thì A sẽ chắc chắn thắng chung cuộc. Chúng ta cần tính những giá trị P(i,j) này với i, j bất kỳ. Lời giải Nếu i=0, j>0, tức là A đã thắng và do đó P(0,j)=1. Nếu i>0, j=0, tức là B đã thắng và A đã thua, do đó P(i,0)=0. Với i, j > 0 ta có nhận xét: sác xuất để A thắng chung cuộc dựa vào ván tiếp theo A thắng hay thua. Nếu ván tiếp theo A thắng, khi đó sác xuất để A thắng sẽ là P(i-1,j), còn nếu A thua ở ván tiếp theo thì sác xuất để A thắng chung cuộc sẽ là P(i,j-1). Vì ván tiếp theo khả năng A thắng thua là 50/50 nên ta có công thức P(i,j) = (P(i-1,j) + P(i,j-1))/2. Tóm lại ta có công thức truy hồi sau để tính P(i,j). Từ công thức (4) với i+j=n ta dễ dàng tính được công thức truy hồi của độ phức tạp tính toán T(n) như sau:T(1) = C(C-const)T(n) = 2T(n-1) + D (D-const) (5) Ta tính được T(n) = O(2n). Như vậy việc tính toán các hệ số P(i,j) sẽ có độ phức tạp tăng theo số mũ của n nếu tính toán bằng kỹ thuật đệ qui và đây là một kết quả rất lớn. Tuy nhiên công thức trên chỉ cho ta giới hạn trên của tính toán, để hiểu rõ hơn thực sự của việc sử dụng đệ qui tính toán theo công thức(4) chúng ta sẽ thử tính toán giới hạn dưới của công việc tính toán này. (Giới hạn dưới của độ phức tạp được ký hiệu là big-omega: W). Để tính được giá trị này chúng ta sẽ tính số lần gọi hàm P khi thực hiện đệ qui cách tính P(i,j) theo công thức (4). Công thức (4) với i+j=n nếu xem xét kỹ sẽ gợi ý cho chúng ta về một đẳng thức tương tự của hệ số tổ hợp là (tổ hợp chập i của n phần tử, số cách chọn ra i phần tử từ tập hợp ban đầu n phần tử). Từ nhận xét trên dễ dàng suy ra rằng số lần gọi hàm P trong P(i,j) sẽ ít nhất là .Với i=j=n/2 dễ thấy giá trị này sẽ bằng . Vậy ta vừa chứng minh được rằng cận dưới độ phức tạp tính toán P(i,j) làlà một giá trị rất lớn (tuy có nhỏ hơn 2n) và hầu như không thể áp dụng tính toán trên thực tế.Cách tính P(i,j) tốt nhất là vừa tính vừa điền số vào bảng như mô tả trong hình 3 dưới đây. Bảng hệ số P(i,j) được điền tuần tự như sau: Trước tiên để ý rằng hàng dưới cùng của bảng là toàn 0 và hàng đầu tiên bên phải sẽ là toàn 1. Xuất phát từ góc phải dưới chúng ta lần lượt điền số vào bảng theo hướng Tây-Bắc dọc theo đường chéo ngược với i+j không thay đổi. Thuật toán điền số P(i,j) vào bảng được mô tả như sau:Function Ods(i,j: integer):real; (7)var s,k:integer;Beginfor s:=1 to i+j dobegin P[0,s]:=1;P[s,0]:=0;for k:=1 to s-1 doP[k,s-k]:=(P[k-1,s-k]+P[k,s-k-1])/2;end;Ods:=(P[i,j]);End; {Ods}Ta hãy thử phân tích thuật toán trên. Vòng lặp bên trong là O(s) thời gian, hai lệnh gán 0 và 1 chỉ là O(1) thời gian, như vậy tổng số thời gian tính từ vòng lặp ngoài sẽ là với n=i+j. Chắc các bạn đã thấy sự kỳ diệu của phương pháp điền bảng số so sánh với việc gọi đệ qui, và đó là tư tưởng của thuật toán quy hoạch động.  2. Một số bài toán nâng cao: a. Bài toán cái túi. Trong siêu thị có n gói hàng (n ≤ 100) gói hàng thứ i có trọng lượng là W[i]≤100 và trị giá V[i] ≤ 100. Một khách hàng đột vào siêu thị, khách hàng mang theo một cái túi có thể mang được tối đa trọng lượng M ( M ≤100 ). Hỏi khách hàng sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất. Input:five văn bản BAG.INP Dòng 1:Chứa hai số n, M cách nhau ít nhất một dấu cách n dòng tiếp theo, dòng thứ I chứa hai số nguyên dương W[i], V[i] cách nhau ít nhất một dấu cách Output: five văn bản BAG.OUT Dòng 1: Ghi giá trị lớn nhất khách hàng có thể lấy Dòng 2: Ghi chỉ số những gói bị lấy Cách giải: Nếu gọi F[i,j] là giá trị lớn nhất có thể có bằng cách chọn các gói {1,2,…., i} với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F[n,M]. Công thức truy hồi tính F[i,j]. Với giới hạn trọng lượng j, việc chọn tối ưu trong số các gói {1,2,…,i-1,i} để có giá trị lớn nhất sẽ có hai khả năng: Nếu không chọn gói thứ i thì F[i,j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1,2,…,i-1} với giới hạn trọng lượng là j. Tức là F[i,j] = F[i-1,j] Nếu có chọn gói thứ i (tất nhiên chỉ xét tới trường hợp này khi mà W[i] ≤ j) thì F[i,j] bằng giá trị gói thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói {1,2,…,i-1} với giới hạn trọng lượng j-W[i]. Tức là về mặt giá trị thu được: F[i,j]=V[i] + F[i-1,j-W[i]] Vì theo cách xây dựng F[i,j] là giá trị lớn nhất có thể, nên F[i,j] sẽ là max trong 2 giá trị thu được ở trên. Dễ thấy F[0,j]= giá trị lớn nhất có thể bằng cách chọn trong số 0 gói= 0. Tính bảng phương án: Bảng phương án F gồm n + 1 dòng, M + 1 cột, trước tiên được điền cơ sở quy hoạch động: Dòng 0 gồm toàn số 0. Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2,v.v… đến khi tính hết dòng n. Tính song bảng phương án thì ta quan tâm đến F[n,M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M. Nếu F[n,M]=F[n -1,M] thì tức là không chọn gói thứ n, ta truy tiếp F[n-1,M]. Còn nếu F[n,M] = F[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F[n-1,M-W[n]]. Cứ tiếp tục cho tới khi truy lên tới hàng 0 của bảng phương án.  P 3 03 5.PAS * Bài toán các túi program The_Bag; const inputfile = ‘BAG.INP’; outputfile = ‘BAG.OUT’; max = 100; var W, V:array[1..max] of integer; F: array[0..max, 0..max] of integer; n, M: integer; procedure enter; var i: integer; fi: text; begin assign(fi, inputfile); reset(fi); readln(fi, n, M) ; for i :=1 to n do readln (fi, W[i], V[i]) ; close(fi) ; end; procedure optimize; {Tính bảng phương án bằng công thức truy hồi} var i, j: integer; begin fillchar(F[0], sizeof (F[0], 0); {Điền cơ sở quy hoạch động} for i :=1 to n do for j :=0 to M do begin {Tính F[i, j]} F[i, j] := F[i-1,j]; if (j >= W[i]) and (F[i,j] <F[i-1, j-W[i]] + V[i]) then F[i,j] := F[i -1, j – W[i]] + V[i]; end; end; procedure trance; {Truy vết tìm nghiệm tối ưu} var fo: text; begin assign (fo, outputfile) ; rewrite(fo); writeln (fo, F[n, M] ; {In ra giá trị lớn nhất có thể kiếm được} while n 0 do {Truy vết trên mảng phương án từ hàng n lên hàng 0} begin if F[n,M] F[n – 1,M] then begin write (fo, n, ‘ ‘); M := M- W[n]; end; dec (n); end; close(fo); end; begin enter; optimize; trace; end; c. Bài toán đổi tiền: Bài toán: Cho n loại giấy bạc, tờ giấy bạc thứ I có mệnh giá A[i]. Số tờ mỗi loại không giới hạn cần chi trả cho khách hàng số tiền M đồng.Hãy cho biết mỗi loại tiền cần bao nhiêu tờ sau cho tổng sồ tờ là ít nhất,nếu không đổi được thì thông báo “ không đổi được”.( n<50, A[i]<256, M<10000) Input: n M A[1] A[2] … A[n] Output: tổng số tờ phải trả, số tờ mỗi loại. Giải thuật: - Cách thứ nhất: Gọi Fx[i,j] là số tờ ít nhất được dùng để trả số tiền j đồng, khi có i lọai tiền từ 1->i (i=1…n; j=1…M).X[i,j] là số tờ giấy bạc loại thứ i được dùng để chi trả số tiền j đồng. Trường hợp đơn giản chỉ có một loại tiền để chọn ta tính Fx[1,j] với mọi j. Fx[1,j] = j div A[1] nếu j mod A[1] = 0 Fx[1,j] = nếu j mod A[1] # 0 Giả sử ta tính được Fx[i-1,j] đến dòng i-1 với mọi j [1,M], khi có thêm loại tiền thứ i để chọn ta cần tính Fx[i,j] ở dòng i với mọi j [1,M]. Nếu ta chọn k tờ loại i thì số tiền còn lại dành cho các loại tiền khác từ loại 1 -> loại i-1 là: u= j – k * A[k]. Khi đó trong tổng số tờ là: Fx[i,j]=Fx[i-1,u] + k, với k thay đổi từ 0 -> kmax, ta chọn giá trị nhỏ nhất và lưu vào Fx[i,j]. Trong đó: kmax=j div A[k] là số tờ nhiều nhất của loại tiền i để đổi số tiền j. => công thức đệ qui là: Fx[i,j]=min(Fx[i-1,j-k*A[i]]+k). min xét với k thay đổi từ 0-> j div A[i] và j-k*A[i] >0 - cách thứ hai: Gọi Fx[i] là số tờ ít nhất được dùng để đổi số tiền i (i=1…M). Với quy ước Fx[i]= (o) khi không đổi được. X[i] là loại tiền cuối cùng dùng để đổi số tiền i. Giải thuật tạo bảng: xếp mệnh giá A[i] tăng dần. Khởi gán Fx[i] =, X[i]= 0. j=1…M Gán Fx[0]=0. với số tiền i chạy từ 1->M, ta tính Fx[i] và X[i], nếu chọn loại tiền j thì số tiền còn lại là i-A[i]. Fx[i]=min( Fx[i-A[j]] +1) nếu i>=A[j] min xét loại tiền j chạy từ 1-> n. X[i]=j ứng với giá trị min của Fx[i]. Dưới đây là mảng Fx[i] và X[i] dùng 3 loại tiền 3,10,12 để đổi 18. i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Fx[i] 1 2 3 1 1 2 2 3 3 X[i] 0 0 1 0 0 1 0 0 1 2 0 3 2 2 0 3 2 0 3 Procedure tạo bảng; Var i: word; j: byte; BEGIN For i:=1 to M do Fx[i]:= ; { = maxInt-1} Fx[0]:=0; FiilChar( X,Sizeof (X), 0); For i:= 1to M do {i là số tiền} For j:= n DownTo 1 do {j là loại tiền} if i>= A[i] then if(Fx[i] > Fx[ i-A[j]]+1) then begin Fx[i]:= Fx[i-A[j]] + 1; X[i]:= j; end; END; III. CHƯƠNG TRÌNH DEMO Chương trình demo này chúng tôi sử dụng Lập trình C để cài đặt và sử dụng một số hàm đồ họa để trang trí chương trình mặc khác làm tăng tính hấp dẫn cho đề tài. Chương trình gồm phần: Input, Taobang, Truyvet, Output. Sau đây là đoạn mã của chương trình. int a[50]; int fx[50][500], b[50]; int n=0, w=0; void taobang() { int i, j, x ; int t ; for ( j=1; j<w; j++) fx[0][j] = j/a[0]*(j%a[0]==0) + (-1)*(j%a[0]!=0); for (i=1; i<n; i++) for (j=1; j<=w; j++) { x=1; fx[i][j] = fx[i-1][j]; while (j >= x*a[i]) { t = fx[i-1][j - x*a[i]] + x; if ((fx[i][j]==-1) || (t < fx[i][j])) if (fx[i-1][j - x*a[i]] != -1) fx[i][j]=t; x++; } } } Void taobang() { int i,j,x; int t; for (j=1; j<=w; j++) fx[0][j] = j/a[0]*(j%a[0]==0) + (-1)*(j%a[0]!=0); (i=1; i<n; i++) for (j=1; j<=w; j++) { x=1; fx[i][j] = fx[i-1][j]; while (j >= x*a[i]) { t = fx[i-1][j - x*a[i]] + x; if ((fx[i][j]==-1) || (t < fx[i][j])) if (fx[i-1][j - x*a[i]] != -1) fx[i][j]=t; x++; } } } Void truyvet() { int i=n-1, j=w; while (j > 0) { while ((fx[i][j] == fx[i-1][j]) && (i > 0)) i--; if (j > 0) { b[i] += fx[i][j] - fx[i][j-a[i]]; j = j-a[i]; } } } Void output() { int i; if (fx[n-1][w] != -1) { truyvet(); for (i=0; i<n; i++) printf("loai %d: %d\n", i+1, b[i]); } else printf("khong doi duoc"); getch(); } Void main() { clrscr(); input(); taobang(); output(); } Trên đây là chương trình dùng để tính toán và đổi tiền. Sau đây là một số hàm đồ họa được sử dụng trong chương trình. void chu3d(int c,int h,int b,int mb,int mc, char st[50]) { int i; for(i=1;i<=b;i++) { setcolor(mb); outtextxy(c+i,h+i,st); } setcolor(mc); outtextxy(c,h,st); } void hoten(int tx,int ty) { char ht1[50],ht2[50]; settextstyle(4,0,3); chu3d(tx+5,ty-10,2,4,10," Tran Khanh Luan"); settextstyle(4,0,3); chu3d(tx+5,ty+20,2,4,10," Le Minh Trieu"); settextstyle(0,0,1); outtextxy(285,405,"MSSV: 2TH1046"); settextstyle(2,0,7); chu3d(tx-30,ty-10,2,2,12, " GV huong dan: "); chu3d(tx-30,ty+20,1,2,12," SV thuc hien: "); settextstyle(1,0,1); chu3d(tx+0,ty+100,2,4,9,"An phim so tuong ung hoac phim mui ten de chon"); } void huong_dan() { setcolor(2); settextstyle(0,0,1); outtextxy(210,10," TRUONG DAI HOC BAC LIEU"); outtextxy(220,30,"KHOA CONG NGHE THONG TIN"); settextstyle(0,0,1); outtextxy(255,50,"===******==="); settextstyle(7,0,1); chu3d(420,130,2,4,10,"NIEN LUAN I"); settextstyle(8,0,4); chu3d(10,80,4,4,15,"BAI TOAN DOI TIEN(quy hoach dong)"); } IV. Phần Kết Luận 1. Kết quả đạt được Sau một thời gian nghiên cứu và tìm hiểu đề tài, cùng với sự hướng dẫn tận tình của thầy cô và sự giúp đỡ của bạn bè. Hôm nay, Niên Luận cơ bản đã được