Sáng kiến kinh nghiệm Thuật toán quay lui và ứng dụng giải bài toán tối ưu

Phần 1: ĐẶT VẤN ĐỀ
Kính thưa quý thầy cô giáo!
Tiến sĩ triều Lê, Thân Nhân Trung đã nói “Hiền tài là nguyên khí của quốc gia, nguyên khí thịnh thì thế nước mạnh mà hưng thịnh, nguyên khí suy thì thế nước yếu mà thấp hèn”. Vì thế các bậc đế vương thánh minh luôn coi việc giáo dục nhân tài, kén chọn kẻ sĩ, vun trồng nguyên khí quốc gia làm công việc hàng đầu..., câu nói bất hủ của Thân Nhân Trung đã cho thấy từ thời xa xưa các thế hệ ông cha đã rất coi trọng nhân tài và coi những nhân tài là tương lai của đất nước. Với cương vị là một giáo viên chuyên ngành Tin học trực tiếp giảng dạy, tôi thấy được những nhiệm vụ quan trọng phải làm đầu tiên đó là làm thế nào để học sinh thích học và học giỏi môn Tin. Trong thời đại ngày nay, Tin học có vai trò và vị trí đặc biệt quan trọng trong khoa học kĩ thuật và đời sống, giúp con người tiếp thu một cách dễ dàng các môn khoa học khác có hiệu quả.
Có thể nói phát hiện và bồi dưỡng HSG là một trong những hoạt động chuyên môn chính trong năm học của trường. Bản thân qua tham khảo các đề thi HSG của tỉnh và quốc gia đã thấy hầu hết các đề thi đều có các bài toán tối ưu. Để giải các bài toán tôi ưu thì có nhiều phương pháp giải, trong đó ứng dụng thuật toán quay lui để giải bài toán tối ưu cũng là một phương pháp được nhiều người sử dụng. Đó cũng chính là lý do để tôi viết đề tài “Thuật toán quay lui và ứng dụng giải bài toán tối ưu”.
Tôi rất mong được sự góp ý của quý thầy cô để đề tài ngày càng được hoàn thiện hơn.
Xin chân thành cảm ơn!
Phần 2: NHỮNG BIỆN PHÁP GIẢI QUYẾT VẤN ĐỀ
I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ:
Cũng như trình bày ở trên bài toán tối ưu là một trong những bài toán thường gặp trong các kỳ thi học sinh giỏi.
Công việc khó khăn ở đây là làm thế nào để các em có thể hiểu được thuật toán và có thể ứng dụng vào giải các bài toán liên quan.
Xuất phát từ thực tiễn như vậy, tôi đã đưa ra một số bước giúp cho các em có thể hiểu được thuật toán và ứng dụng để giải các bài toán cùng loại:
Ý tưởng của thuật toán.
Thuật toán.
Ứng dụng thuật toán giải các bài toán đơn giản.
Ứng dụng thuật toán quay lui có đánh giá cận giải một số bài toán phức tạp.
Ứng dụng thuật toán giải bài toán trong các đề thi học sinh giỏi.
II. THỰC TRẠNG CỦA VẤN ĐỀ:
1) Thực trạng về cấp quản lý
	*) Ưu điểm:
	- Đã quan tâm vào công tác phát triển mũi nhọn.
	- Có sự phân công nhiệm vụ cho từng giáo viên trực tiếp giảng dạy, giám sát và kiểm tra quá trình thực hiện của giáo viên.
	- Động viên tinh thần cũng như tạo mọi điều kiện thuận lợi nhất để giáo viên thực hiện nhiệm vụ.
	*) Hạn chế:
Khi phân công nhiệm vụ thì chưa xác định một chiến lược lâu dài, đó là chỉ tập trung phát hiện và bỗi dưỡng học sinh lớp 11 mà không phát hiện và bồi dưỡng ngay từ khi các em đang học lớp 10.
2) Thực trạng về giáo viên
	*) Ưu điểm:
- Được đào tạo về chuyên môn cơ bản, có sức khỏe, sức trẻ, có lòng nhiệt tình trong công việc. Luôn luôn học tập trau dồi tri thức, nhằm phục vụ tốt nhất cho sự nghiệp giáo dục.
- Trong quá trình giảng dạy, tuy gặp nhiều khó khăn nhưng phần lớn các thầy cô giáo đều đặt chữ “tâm” lên hàng đầu, đây là một trong những thuận lợi góp phần vào sự thành công của ngành giáo dục.
	- Có sự đầu tư vào nghiên cứu khi được giao nhiệm vụ.
	*) Hạn chế:
Một số giáo viên không có tâm huyết, chưa tập trung vào công tác chuyên môn nên kiến thức về ôn luyện học sinh giỏi còn hạn chế. Việc bồi dưỡng HSG chỉ tập trung cho số ít giáo viên trong tổ.
3) Thực trạng về học sinh 
*) Ưu điểm:
- Các em HS ngoan, cần cù chịu khó, có ý thức vươn lên trong học tập.
- Có trách nhiệm với việc học tập, trong quá trình học tập hăng say phát biểu, đóng góp nên sự thành công của bài giảng.
*) Hạn chế:
- Kiến thức cơ bản về lập trình còn rất nhiều hạn chế, chỉ có số ít em học sinh trên địa bàn thị trấn, mới được tiếp cận với lập trình ở chương trình lớp 8 – THCS.
- Đa số các em học tốt môn Tin học thì lại học tốt các môn khoa học tự nhiên (Toán, Lí, Hóa), nên đã theo tham gia bồi dưỡng ở các bộ môn đó.
- Tin học là môn mà không có trong các kỳ thi tốt nghiệp cũng như đại học hàng năm, nên các em cũng không mặn mà với việc tham gia học và bồi dưỡng HSG.
4) Thực trạng về cơ sở vật chất
	*) Ưu điểm:
	- Có đủ cơ sở vật chất để phục vụ cho lớp học.
	- Có các phương tiện phục vụ cho mục đích giảng dạy , VD: Bảng từ, máy chiếu, máy tính...
*) Hạn chế:
	- Thiếu tài liệu và sách tham khảo.
	- Một số học sinh không có đủ kinh phí mua máy tính cá nhân phục vụ cho mục đích ôn tập tại nhà.
III. CÁC BIỆN PHÁP ĐÃ TIẾN HÀNH ĐỂ GIẢI QUYẾT VẤN ĐỀ:
1. Thuật toán quay lui: Giả thiết một cấu hình cần tìm được mô tả bởi một bộ phận gồm n thành phần a1, a2,...an. Giả sử tìm được i - 1 thành phần a1, a2, ai-1, ta tìm thành phần thứ i bằng cách duyệt tất cả các khả năng có thể của ai. Với mỗi khả năng j kiểm tra xem nó có chấp nhận được không. Xảy ra hai trường hợp:
- Chấp nhận được thì xác định ai theo j và kiểm tra xem i = n chưa, nếu i = n thì ta ghi nhận một cấu hình, còn nếu i <n ta tiến hành xác định ai+1.
- Nếu thử tất cả các khả năng mà không có khả năng nào chấp nhận được thì quay lại bước trước xác định lại ai-1.
Nội dung của thuật toán này rất phù hợp với việc gọi đệ quy. Ta có thủ tục đệ quy sau đây:
Procedure Try (i:tinteger);
Var j:integer;
Begin
 For j:=1 to n do 
 if chấp nhận j then
 Begin
 xác nhận ai theo j
 if i=n then 
 Else try(i+1);
 End;
End;
2. Ứng dụng thuật toán quay lui giải một số bài toán cơ bản:
Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài n.
Bài 2: Hãy viết chương trình liệt kê các hoán vị của {1,2,...,n}
Bài 3: Hãy viết chương trình liệt kê các tổ hợp chập m của {1,2,...,n}
Bài 4: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao cho chúng không ăn được nhau.
Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình Haminton của đơn đồ thị vô hướng. (Chu trình bắt đầu từ đỉnh v nào đó qua tất cả các đỉnh còn lại, mỗi đỉnh đúng một lần rồi quay trở về đỉnh v được gọi là chu trình Hamilton).
(*Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài n.*)
Giải: Biểu diễn dãy nhị phân dưới dạng b1,b2,...,bn trong đó biÎ{0,1}. Thủ tục đệ quy Try(i) xác định bi, trong đó các giá trị đề cử là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không phải thỏa mãn điều kiện gì (vì vậy bài toán không cần biến trạng thái). Thủ tục Init nhập giá trị n và khởi gán biến đếm Count. Thủ tục result đưa ra dãy tìm được.
Program Day_nhi_phan;
Uses Crt;
Var b:array[1..20] of 0..1;
 n:Integer; count:byte;
Procedure Init;
Begin
 Write('Nhap n='); readln(n);
 Count:=0;
End;
Procedure Result;
Var i:integer;
Begin
 Count:=count+1; Write(Count:5,'.');
 For i:=1 to n do write(b[i]:3); writeln;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
 For j:=0 to 1 do
 Begin
 b[i]:=j;
 if i=n then result Else try(i+1);
 End;
End;
BEGIN
 Clrscr;
 Init;
 try(1);
 Readln;
END.
(*Bài 2: Hãy viết chương trình liệt kê các hoán vị của {1,2,...,n}*)
Giải: Biểu diễn hoán vị dưới dạng p1,p2,...,pn, trong đó pi nhận các giá trị từ 1 đến n và pi¹pj với i¹j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy cần được ghi nhớ đối với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy biến logic bj, trong đó bj bằng True nếu j chưa được dùng. Các biến này cần được gán giá trị True trong thủ tục Init. Sau khi gán j cho pi cần ghi nhận False cho bj và phải gán lại giá trị True sau khi thực hiện xong Result.
Program Liet_ke_hoan_vi;
Uses Crt;
Var n:Integer;
 p:array[1..20] of integer;
 b:array[1..20] of boolean;
 Count:Word;
Procedure Init;
Var i:Integer;
Begin
 Write('Nhap n='); readln(n);
 For i:=1 to n do b[i]:=true;
 count:=0;
End;
Procedure Result;
Var i:integer;
Begin
 Count:=count+1;
 Write(Count:5,'.');
 For i:=1 to n do write(p[i]:3);
 Writeln;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
 For j:=1 to n do
 if b[j] then
 Begin
 p[i]:=j;
 b[j]:=false;
 if i=n then result Else try(i+1);
 b[j]:=true;
 End;
End;
BEGIN
 Clrscr;
 init;
 try(1);
 Readln;
END.
(* Bài 3: Hãy viết chương trình liệt kê các tổ hợp chập m của {1,2,...,n}*)
Giải: Biểu diễn tổ hợp dưới dạng c1c2...cm, trong đó:
Từ đó suy ra các giá trị đề cử cho ci là từ ci-1+1 đến n. Để điều này đúng cho cả trường hợp i=1, cần thêm vào c0 với c0=0. Các giá trị đề cử này mặc nhiên được chấp nhận. Các thủ tục Init, result được xây dựng giống như bài toán trước.
Program Liet_ke_to_hop;
Uses Crt;
Var n,m:integer;
 c:array[0..20] of integer;
 count:word;
Procedure Init;
Begin
 Write('n,m='); readln(n,m);
 c[0]:=0; Count:=0;
End;
Procedure result;
Var i:integer;
Begin
 Count:=count+1;
 Write(Count:5,'.');
 For i:=1 to m do write(c[i]:3);
 writeln;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
 For j:=c[i-1]+1 to n do
 Begin
 C[i]:=j;
 if i=m then result Else try(i+1);
 End;
End;
BEGIN
 Clrscr;
 Init; Try(1);
 Write('Go Enter de ket thuc!');
 Readln;
END.
(* Bài 4: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao cho chúng không ăn được nhau *)
Giải: Ta xếp n con hậu trên n dòng, Theo nguyên lý nhân ta có nn cách sắp xếp thoả mãn điều kiện đầu bải. Để làm điều đó ta dùng thủ tục đệ quy mô tả ở trên để giải. Ta đánh ghi số cột và dòng của bàn cờ từ 1 đến n, mỗi cách sắp xếp ứng với 1 bộ gồm a1,a2,.....,an với ai = j (j=1,2,...,n) có nghĩa là con hậu thứ i đặt vào cột j. Giả sử ta chọn được i-1 con hậu bằng cách duyệt tất cả các khả năng của nó. 
Quan trọng nhất là ta tìm điều kiện chấp nhận j, một con hậu đứng ở một ô trong bàn cờ nó có nhiều nhất bốn hướng đi (đường dọc, đường ngang và hai đường chéo).
Vậy điều kiện chấp nhận thứ i thoả mãn không nằm trên đường đi của tất cả i-1 con hậu đã xếp. Bởi vì n con hậu xếp ở n hàng nên đường đi ngang của chúng là không chiếu nhau, do đó khi chọn con hậu thư i chỉ cần kiểm tra xem trên 2 đường chéo và đường dọc của chúng có chiếu vào những con hậu đã xếp không? Để kiểm tra điều này mỗi đường ta dùng một biến trạng thái.
* Đường dọc kiểm soát bằng biến a[j],(j=1,2,...,n).
* Một đường chéo kiểm soát bằng biến b[i+j],i+j={2,....,2n}.
* Còn đường chéo kia kiểm soát bằng biến c[i-j],i-j={1-n,....,n-1}.
Các biến trạng thái này khởi gán giá trị True trong thủ tục Init. Như vậy con hậu thứ i được chấp nhận xếp vào cột j nếu nó thoả mãn cả ba biến a[j],b[i+j],c[i-j] đều có giá trị true. Các biến này gán giá trị False khi xếp xong con hậu thứ i, và trả lại giá trị true sau khi gọi Result hay Try(i+1). Ta có chương trình Pascal sau:
Program XepHau;
Uses crt;
Var 	 n : integer;
x:array[1..30] of integer;
a:array[1..30] of boolean;
b:array[2..60]of boolean;
c:array[-19..19] of boolean;
count:word;
Procedure Init;
Var i:integer;
Begin
Write('Cho do rong ban co n= ');
Readln(n);
Count:=0;
For i:=1 to n do a[i]:=true;
For i:=2 to 2*n do b[i]:=true;
For i:=1-n to n-1 do c[i]:=true;
End;
Procedure Result;
Var i:integer;
Begin
count:=count+1;
Write('Cach xep thu',count:5,'.');
for i:=1 to n do write(a[i]:2); Writeln;
End;
Procedure try(i:integer);
Var j : integer;
Begin
 For j:=1 to n do
 If (a[j]) and (b[i + j]) and (c[i - j]) then
 Begin
 x [i] : = j;
 a [j] : = false;
 b[i + j]: = false;
 c [i-j] : = false;
 if i = n then Result Else try (i+1);
 a [j] : = true;
 b[i + j]: = true;
 c[i - j]: = true;
 End;
End;
BEGIN
 clrscr;
 Init;
 Try(1);
 Write ('An Enter de ket thuc:');
 Readln;
END.
(*Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình Haminton của đơn đồ thị vô hướng *)
Giải: 
Program Chutrinhhamilton; 
Const max=100; 
var   	f:Text; 
  	a:array[1..max, 1..max] of Boolean;  
  	Chuaxet:array[1..max] of Boolean;  
  	X:array[1..max] of Integer;  
  	n:Integer; 
procedure Enter;                 
var i,u,v,m: Integer; 
Begin 
 FillChar(a,SizeOf(a),False);{tạo ra 1 mảng được gán, in ra là false} 
 ReadLn(f1,n,m); 
 for i:=1 to m do 
  begin 
   	ReadLn(f1,u,v); 
   	a[u,v]:=True;  a[v,u]:=True; 
  end; 
end; 
procedure PrintResult;           
 var i:Integer; 
  begin 
Writeln('CO TON TAI CHU TRINH EULER');   
for i:=1 to n do Write(f2, X[i],'->'); 
   	WriteLn(f2,X[1]); 
  end; 
procedure Try(i:Integer);    
var j:Integer; 
Begin 
     for j:=1 to n do                 
     if Chuaxet[j] and a[x[i-1],j] then  
    begin 
        	x[i]:=j;                       
        	if i < n then                   
      	begin 
           	Chuaxet[j]:= False;  
           	Try(i+1);        
           	Chuaxet[j]:= True;     
      	end                   
        else                             
      if a[j,X[1]] then PrintResult;                                    
   end; 
End; 
BEGIN 
    Assign(F1, 'HAMILTON.INP'); Reset(F1); 
    Assign(F2, 'HAMILTON.OUT'); Rewrite(F2); 
    Enter; 
    FillChar(Chuaxet,n,True);         
    x[1]:=1; Chuaxet[1]:=False;     
    Try(2);                       
    Close(F1); 
    Close(F2); 
END.
3. Phương Pháp Nhánh Cận (Branch and Bound)
(Bài toán cái túi và bài toán người du lịch)
a. Nội dung:
Đặt vấn đề 
Ý tưởng 
Thuật giải 
Cài đặt 
Đánh giá 
Ví dụ minh họa 
b. Đặt vấn đề:
Bài toán thực tế: Bài toán người giao hàng.
Một người cần phải giao hàng tại N thành phố T1, T2, , Tn. 
Cij: chi phí đi từ thành phố Ti đến thành phố Tj (i=1,2,,N; j = 1,2,,N).
Yêu cầu: xác định hành trình thỏa mãn đi qua tất cả các thành phố, mỗi thành phố qua đúng 1 lần, rồi quay trở lại thành phố xuất phát. Chi phí nhỏ nhất.
 Cách 1 giải quyết bài toán: 
Phương pháp vét cạn.
Phương pháp vét cạn quay lui .
Một số phương pháp khác.
Nhược điểm: Phải xét cả những phương án không khả thi (gây bùng nổ tổ hợp khi dữ liệu đầu vào n lớn) 
Cách 2 giải quyết bài toán:
Mô hình thành phố.
Sử dụng thuật toán quay lui.
c. Ý tưởng (cách 2):
Giữ lại 1 phương án mẫu. 
Tính chi phí của các phương án khác ngay trong quá trình xây dựng. 
Nếu tốt hơn: Cập nhật lại phương án mẫu và đi tiếp.
Không tốt hơn: Quay lại bước trên xét phương án khác.
d. Thuật giải:
Bài toán tối ưu: Tìm min{f(x): x Î D} 
Khái niệm bài toán tối ưu: Hãy lựa chọn trong số các cấu hình tổ hợp chấp nhân được cấu hình có giá trị tốt nhất.
Nghiệm bài toán có dạng x= ( x1,x2,,xn ). 
Bước 1: Xuất phát từ x1, xây dựng một phương án mẫu f* 
Bước i: Đã xây dựng được nghiệm thành phần (x1, x2,, xi-1) 
Đánh giá cận: tìm g xác định trên xi: 
g(x1,,xi) < Min {f(a): a=(a1,,an) thuộc x, xi=ai, i=1,,n} 
Giả sử x* là lời giải tốt nhất tại thời điểm đó, f* là giá trị tốt nhất f*=f(x*) 
Nếu f*<g có thể bỏ đi không cần phát triển lời giải bộ phận (x 1 ,,x i) 
Ngược lại: tiến hành bước i+1 để xác định xi+1. 
e. Cài đặt:
Try(i) 
for ( j=1->n ) if ( chấp nhận được j) {Xác định xi theo j; Ghi nhận trạng thái mới}
if ( i=n ) Cập nhật lời giải tối ưu
Else { Xác định cận g(x1,,xi); if ( g(x1,,xi) < f* ) Try(i+1)}}} 
f. Đánh giá: 
Ưu điểm: Giảm được chi phí: do loại bỏ được những bước đi không cần thiết (nhờ đánh giá cận).
Nhược điểm:Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. Hàm g phải đảm bảo điều kiện: 
Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tổ hợp tìm 
min= min{f (a): a=(a1 ,,an) thuộc x, xi =ai , i=1,,n} 
Giá trị của g(a1, a2 ,, ak) phải sát với các giá trị của min. 
g. Ví dụ minh họa:
Bài 1: Bài toán cái túi
Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có n đồ vât có thể mang theo (số lượng mỗi loại là không hạn chế). Đồ vật thứ j có trọng lượng aj và giá trị sử dụng cj (j=1,2,...,n). Hỏi nhà thám hiểm cần đem theo những loại đồ vật nào, số lượng mỗi loại là bao nhiêu để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất?
Mô hình toán học của bài toán có dạng sau: Tìm
Trong đó: 	xj là số lần lấy đồ vật j.
	cj là giá trị đồ vật j.
aj là trọng lượng đồ vật j.
Dưới đây là chương trình pascal giải bài toán cái túi theo thuật toán quay lui có đánh giá cận với các biến sử dụng trong chương trình là:
(* Cost: Tổng giá trị các đồ vật chứa trong túi tại thời điểm đang xét *)
(* Fopt: Giá trị kỷ lục đến tại thời điểm đang xét *)
(* Xopt: Mảng chứa số lần lấy các đồ vật đã bỏ vào túi *)
(* Weight: Trọng lượng của cái túi tại thời điểm đang xét *)
(* c[i]: Giá trị đồ vật thứ i *)
(* a[i]: Trọng lượng đồ vật thứ i *)
(* n: Số lượng đồ vật đã cho *)
(* w: Trọng lượng toàn bộ cái túi có thể chứa *)
(* ind(i): Ghi nhận vị trí ban đầu của đồ vật i *)
(* x[i]: Số lần lấy đồ vật thứ i *)
Uses Crt;
Const inf=25000;
Type arrn=array[1..50] of integer;
 arrnl=array[1..50] of real;
Var c,a : arrnl;
 x,xopt, ind : Arrn;
 n : Integer;
 w,fopt,cost,weight: Real;
Procedure Khoitao;
Var i,j,tg: integer;
 t:real;
Begin
 Fopt:=0; Weight:=0; {Tong gia tri, trong luong ban dau cua tui la 0 }
 For i:=1 to n do ind[i]:=i; {Ghi nhan thu tu ban dau cua cac do vat }
(* Sap xep do vat theo thu tu khong tang cua c[i]/a[i] nham som tim thay cau hinh tot nhat*)
 For i:=1 to n-1 do
 Begin
 For j:=i+1 to n do
 if (c[i]/a[i]<c[j]/a[j]) then
 Begin
 t:=c[i]; c[i]:=c[j]; c[j]:=t;
 t:=a[i]; a[i]:=a[j]; a[j]:=t;
 tg:=ind[i]; ind[i]:=ind[j]; ind[j]:=tg;
 End;
 End;
End;
Procedure readfile;
Var j: integer;
 f: text;
 Name: String;
Begin
 Write('Cho ten file du lieu:'); readln(name);
 Assign(f,name);
 Reset(f);
 Readln(f,n,w);
 For j:=1 to n do read(f,a[j]);
 readln(f);
 For j:=1 to n do read(f,c[j]);
 Close(f);
 Writeln('Trong luong cai tui: ',w:4:0);
 Writeln('VEC TO GIA TRI DO VAT:');
 For j:=1 to n do write(c[j]:4:0); writeln;
 Writeln('VEC TO TRONG LUONG DO VAT:');
 For j:=1 to n do write(a[j]:4:0); writeln;
End;
Procedure Ghinhan_ky_luc;
Var i:integer;
Begin
{Neu tong gia tri cua cac do vat tai cau hinh dang xet > gia tri ky luc truoc do thi cap nhat lai cau hinh tot hon}
 if Cost>fopt then
 Begin
 xopt:=x; {Ghi nhan cau hinh do vat moi}
 Fopt:=cost;{Ghi nhan gia tri moi cua tui}
 End;
End;
Procedure Nhanh_can(i:integer);
Var j,t:integer;
Begin
t:=trunc((w-weight)/a[i]); {Trong luong con lai cua tui co the chua bao 	nhieu do vat thu i}
 For j:=t downto 0 do
 Begin
 x[i]:=j;
 weight:=weight+a[i]*x[i];
 Cost:=cost+c[i]*x[i];
 if i=n then Ghinhan_ky_luc
 Else
 if cost+c[i+1]*(w-weight)/a[i+1]> fopt then Nhanh_can(i+1);
 weight:=weight-a[i]*x[i];
 Cost:=cost-c[i]*x[i];
 End;
End;	
Procedure Inkq;
Var i,j:integer;
Begin
 Writeln('********** KET QUA TINH TOAN ***********');
 Writeln('Tong gia tri cua cac do vat: ', fopt:4:0);
 Writeln('Phuong an lay do:');
 For j:=1 to n do writeln('So luong do vat ',ind[j],' la: ',xopt[j]:4,' lan');
 Writeln('******************************************');
 Write('Nhan enter de tiep tuc'); readln;
End;
BEGIN
 Clrscr;
 Readfile;
 Khoitao;
 Nhanh_can(1);
 Inkq;
 Readln;
END.
Giả sử ta có File dữ liệu là Caitui.txt trong ổ G có nội dung:
4 20
3 5 4 6
20 10 8 15
Thì sau khi chay xong chương trình ta có kết quả:
Cho ten file du lieu: G:\caitui.txt
Trong luong cai tui:	20
VEC TO GIA TRI DO VAT:
 20 10 8 15
 3 5 4 6
 ********KET QUA TINH TOAN*********
	Tong gia tri cua cac do vat:	120
	Phuong an lay do:
	So luong do vat 1 la: 6 lan.
	So luong do vat 4 la: 0 lan.
So luong do vat 3 la: 0 lan.
	So luong do vat 2 la: 0 lan.
	********************************************
Bài 2: Bài toán người du lịch
Một người du lịch muốn đi tham quan n thành phố T1, T2,..., Tn. Xuất phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay lại thành phố xuất phát. Cij là chi phí đi từ thành phố Ti đến thành phố Tj (i,j=1,2,...,n), hãy tìm một hành trình (một cách đi thỏa mãn điều kiện đặt ra) với tổng chi phí nhỏ nhất.
Cố định thành phố xuất phát là T1, bài toán người du lịch dẫn về bài toán:
Với điều kiện (x2,x3,...,xn) là hoán vị của các số 2,3,...,n.
Ký