Chuyên đề Niên luận kỹ thuật nhánh cận

MỤC LỤC PHẦN I: TỔNG QUAN I.GIỚI THIỆU CHUNG Trang 2 II. MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT Trang 2 PHẦN II: LÝ THUYẾT VÀ ỨNG DỤNG Trang 4 I. BÀI TOÁN ĐƯỜNG ĐI CỦA NGƯỜI GIAO HÀNG Trang 4 II. BÀI TOÁN CÁI BA LÔ Trang 12 PHẦN III: CHƯƠNG TRÌNH DEMO Trang 25 I. HƯỚNG DẪN CÀI ĐẶT CHƯƠNG TRÌNH Trang 25 II. HƯỚNG DẪN SỬ DỤNG Trang 25 PHẦN IV: KẾT LUẬN Trang 28 I. NHẬN XÉT KẾT QUẢ ĐẠT ĐƯỢC Trang 28 II. NHỮNG MẶT HẠN CHẾ Trang 28 III. HƯỚNG PHÁT TRIỂN Trang 28 TÀI LIỆU THAM KHẢO Trang 29 PHẦN I: TỔNG QUAN GIỚI THIỆU CHUNG: Niên luận được xem như là đề tài dành cho sinh viên năm 3 chuyên ngành Công Nghệ Thông Tin (CNTT). Niên luận giúp cho sinh viên tự nghiên cứu, tự đánh giá khả năng học tập của mình trong suốt thời gian học vừa qua. Mỗi sinh viên sẽ bóc thăm chọn cho mình một đề tài. Sinh viên tự tìm tài liệu, tự nghiên cứu về đề tài của mình. Đồng thời với kiến thức các môn học cơ sở ngành và dưới sự hướng dẫn của giáo viên để viết chương trình demo và một quyển báo cáo niên luận theo yêu cầu. Đề tài niên luận của em là: “CHUYÊN ĐỀ KỸ THUẬT NHÁNH CẬN”. Nội dung đề tài này em đã được học ở bô môn “Giải thuật”. Đây là một trong những kỹ thuật thiết kế giải thuật. Và kỹ thuật “nhánh cận” là một trong những kỹ thuật tối ưu nhất của kỹ thuật quay lui. Yêu cầu của đề tài: trình bày cơ sở xuất phát và nội dung kỹ thuật nhánh cận. Tuyển chọn ít nhất 3 bài toán có thể giải bằng kĩ thuật nhánh cận. Mỗi bài cần mô tả cấu trúc dữ liệu, giải thuật thực hiện, độ phức tạp của giải thuật và cài đặt chương trình. Đây là niên luận đầu tiên nên không tránh khỏi sai xót trong quá trình làm. Mong thầy cô thông cảm và đóng góp ý kiến chân tình để em rút kinh nghiệm cho bài niên luận sau tốt hơn. Chân thành cảm ơn quý thầy cô!!! MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT 1. Mục tiêu cần đạt được: Lý thuyết: - Cần hiểu và nắm rõ các giải thuật của kỹ thuật “nhánh cận” trong môn học “giải thuật”. - Hiểu các kiểu cấu trúc dữ liệu và áp dụng một kiểu phù hợp để cài đặt cho chương trình. - Nắm vững ngôn ngữ lập trình C nhằm giải quyết một cách hiệu quả các vấn đề đặt ra. - Đưa ra các bài toán có thể giải bằng phương pháp nhánh cận, ứng dụng lý thuyết giải đúng các bài toán đề ra. - Trình bày nội dung rõ ràng, chặt chẽ và dễ hiểu. Với nội dung và hình thức sao cho đúng với yêu cầu. Về chương trình demo: - Phải thiết kế chương trình đúng với giải thuật có sẵn. Chương trình chạy đúng, và chọn phương án tối ưu nhất để viết chương trình. - Cung cấp giao diện thân thiện với người dùng. 2. Hướng giải quyết: Với các yêu cầu đặt ra ta có thể giải quyết các vấn đề như sau: a)Về cấu trúc dữ liệu: - Dữ liệu dầu vào được nhập từ bàn phím. - Về cấu trúc cài đặt: sử dụng danh sách liên kết để viết chương trình con nhập các đồ vật cho bài toán cái ba lô. - Bên cạnh đó xây dựng nhiều chương trình con: sắp xếp, phân nhánh, quay lui, kết quả, và thoát chương trình. Và chương trình chính để gọi các chương trình con thực hiện. b)Về ngôn ngữ lập trình: Sau khi tìm hiểu và so sánh một số ngôn ngữ lập trình gồm: Pascal, C, C++… em quyết định chọn ngôn ngữ lập trình C để cài đặt chương trình Demo với các lý do sau: - C là ngôn ngữ lập trình khá sinh động và phổ biến. - C hỗ trợ các thư viện đáp ứng được các hàm dùng để sử lý chuỗi thích hợp với đề tài của em. - Chọn cấu trúc danh sách để cài đặt. - Ngoài ra, C là ngôn ngữ mà em am hiểu và ưu thích. PHẦN II: LÝ THUYẾT VÀ ỨNG DỤNG Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả các phương án thì mất rất nhiều thời gian, nếu sử dụng phương pháp tham ăn thì phương án tìm được chưa hẳn đã là phương án tối ưu. Nhánh cận là kỹ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh. Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có , mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n. Kỹ thuật này được gọi là phân nhánh. Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án. Với bài toán tìm Min ta sẽ xác định cận dưới, còn với bài toán tìm Max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án. Để dễ hình dung ta sẽ xét hai bài toán quen thuộc là bài toán TSP và bài toán cái ba lô. BÀI TOÁN ĐƯỜNG ĐI CỦA NGƯỜI GIAO HÀNG: 1. Giới thiệu: Bài toán tìm đường đi của người giao hàng là có một người giao hàng cần đi giao hàng tại n thành phố T1, T2… Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần. Biết Cij là chi phí đi từ thành phố Ti thành phố Tj (I = 1, 2, 3,…, n), hãy tìm hành trình với tổng chi phí là nhỏ nhất (một hành trình là một cách đi thỏa mãn điều kiện. 2. Hướng giải quyết: - Cố định thành phố xuất phát là T1. Bài toán người đi giao hàng được đưa về bài toán: tìm cực tiểu của phiếm hàm: F(x1, x2, …, xn) = c[1,x1]+c[x2,x3]+…+c[xn-1,xn]+c[xn,x1]→ min - Với điều kiện - Cmin = min{c[i,j],I,j = 1,2,…, n;i ≠ j là chi phí đi lại giữa các thành phố. - Giả sử ta đang có phương án bộ phận (u1,u2,…,uk). Phương án tương ứng với hành trình bộ phận qua k thành phố: T1→T(u2)→…→T(uk-1)→(uk) -Vì vậy chi phí phải trả theo hành trình bộ phận này sẽ là tổng các chi phí theo từng node của hành trình bộ phận. ∂=c[1,u2]+c[u2,u3]+…+c[uk-1,uk] - Để phát triển hành trình bộ phận này thành hành trình đầy đủ, ta còn phải đi qua n-k thành phố còn lại rồi quay trở về thành phố T1, tức là còn phải đi qua n-j+1 đoạn đường nữa. Do đó chi phí phải trả cho việc đi qua mỗi trong n-k+1 đoạn đường còn lại đều không nhiều hơn cmin, nên cận dưới cho phương án bộ phận (u1, u2,…, uk) có thể được tính theo công thức g(u1, u2, …, uk) =∂+(n-k+1)cmin 3. Sau đây là giải thuật của giải bài toán này: a) Đầu tiên ta phải nhập tên các cạnh và trọng số của các đỉnh. Chương trình con nhập được thiết kế là ma trận vuông. Số dòng và cột bằng nhau và bằng số đỉnh đã cho. Đồng thời sắp xếp tên các cạnh theo thứ tự từ điển để xét phân nhánh. Dưới đây là lưu đồ cho phần nhập: end Begin i<=n; j<=n i=1; j=1 Tăng i, j lên 1 Nhập n, C[i][j] In C[i][j] Dữ liệu được lấy từ trong tập tin test2.txt. Sai Đúngg Code được viết như sau: void Nhap_dulieu(void) { int i, j; FILE *fp; //Doc du lieu tu trong tap tin fp = fopen("E:\\nhanhcan\\test2.txt","r"); fscanf(fp,"%d", &n); printf("\n\t So thanh pho nhap vao la: %d\n",n); printf("\n\t Ma tran chi phi nhap vao la: "); for (i=1; i<=n; i++) { printf("\n\n"); for(j=1; j<=n; { fscanf(fp,"\t %d",&C[i][j]); printf("\t %5d", C[i][j]); } printf("\n"); } } b) Tính cận dưới: - Cận dưới tại mỗi nút là một số nhỏ hơn hoặc bằng giá của tất cả các phương án được biểu diễn bởi nút đó. Giá của một phương án ở đây là tổng độ dài của một chu trình. - Cận dưới cho nút gốc, mỗi đỉnh ta chọn hai cạnh có độ dài nhỏ nhất từ ma trận Lưu đồ chọn hai cạnh có độ dài nhỏ nhất: Begin ij && min > C[i][j] Tăng i, j lên 1 end In min min =1000, i =1, j = 1 i<=n; j<=n min = C[i][j] Sai Đúng Sai Đúng Code được viết như sau: int Min_Matrix(void) { int min=1000, i, j; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if (i!=j && min>C[i][j]) min=C[i][j]; } } return(min); } - Cận dưới của nút gốc bằng tổng độ dài tất cả các cạnh được chọn chia cho 2. - Đối với các nút khác, chúng ta phải lựa chọn hai cạnh có độ dài nhỏ nhất thỏa điều kiện ràng buộc (phải chứa cạnh này, không chứa cạnh kia). c) Phân nhánh: - Bước đầu tiên phải tạo nút gốc: Nút gốc là nút biểu diễn cho cấu hình bao gồm tất cả các phương án. Và xác định cận dưới cho nút gốc. - Sau đó phân nhánh cho các nút : + Mỗi nút sẽ có hai con: con trái biểu diễn cho cấu hình bao gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình bao gồm tất cả các phương án không chứa cạnh đó. Sau khi phân nhánh cho mỗi nút, ta tính cận dưới cho cả hai con. + Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới. + Nếu cận dưới của một nút con lớn hơn hoặc bằng giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì ta không cần xây dựng các cây con cho nút này nữa, hay ta gọi là cắt tỉa. + Nếu cả hai con đều có cận dưới nhỏ hơn giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì nút con nào có cận dưới nhỏ hơn sẽ được ưu tiên phân nhánh trước. + Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án. Để quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu. - Mỗi lần quay lui để xét nút con chưa được xét của một nút ta phải xem xét lại nút con đó để có thể cắt tỉa các cây của nó hay không vì có thể một phương án có giá nhỏ nhất tạm thời vừa được tìm thấy. - Sau khi tất cả các con đã được phân nhánh hoặc bị cắt tỉa thì phương án có giá nhỏ nhất trong các phương án tìm được là phương án cần tìm. 4. Lưu đồ khối minh họa cho chương trình chính: Begin end Menu xử lý Nhập dữ liệu In kết quả Chương trình 5. Bài toán ứng dụng phần cho giải thuật trên: Xét bài toán TSP có 4 đỉnh với độ dài các cạnh được cho trong hình là: A 3 B 11 1 5 9 D 7 C Giải bài toán trên bằng giải thuật nhánh cận. Dựa vào giải thuật nhánh cận ta có được cây phân nhánh sau: Tất cả các phương án 16 AB 16 23 AC, 25 BD, 21 AD, 16 BC, 16 Tạo thành chu trình thiếu CD ABCDA 16 Ta thấy tất cả các nút con của cây đã được xét hoặc bị cắt tỉa nên phương án cần tìm là ABCBA với giá là: 16. BÀI TOÁN CÁI BA LÔ: 1. Giới thiệu: Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật i có một trọng lượng gi và một giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế hoặc hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các loại đồ vật nào mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất. 2. Sau đây là giải thuật của giải bài toán này: - Bước 1: + Đầu tiên ta phải nhập các dữ liệu đề bài cho: tên đồ vật, giá trị, trọng lượng, số lượng(nếu có)… Viết 2 chương trình con nhập: nhap1 ( là ba lô không có giới hạn số lượng đồ vât), nhap2 ( là ba lô có giới hạn số lượng đồ vật). Code nhập ba lô không có giới hạn: for(int i=1;i<=n;i++) { printf("\n\n NHAP DU LIEU CHO DO VAT THU %d : \n",i); printf("\n\t Ten do vat : "); scanf(" %s",&(Ds_vat[i-1].Ten)); printf("\n\t Trong luong: "); scanf(" %d",&(Ds_vat[i-1].Trong_luong)); printf("\n\t Gia tri : "); scanf(" %d",&(Ds_vat[i-1].Gia_tri)); Ds_vat[i-1].Don_gia = float(Ds_vat[i-1].Gia_tri)/float(Ds_vat[i-1].Trong_luong); printf("\n\t Don gia : %.2f",Ds_vat[i-1].Don_gia); } Code nhập ba lô có giới hạn: for(int i=1;i<=n;i++) { printf("\n\n NHAP DU LIEU CHO DO VAT THU %d : \n",i); printf("\n\t Ten do vat : "); scanf(" %s",&(Ds_vat[i-1].Ten)); printf("\n\t So luong : "); scanf("%d",&(Ds_vat[i-1].So_luong)); printf("\n\t Trong luong: "); scanf(" %d",&(Ds_vat[i-1].Trong_luong)); printf("\n\t Gia tri : "); scanf(" %d",&(Ds_vat[i-1].Gia_tri)); Ds_vat[i-1].Don_gia = float(Ds_vat[i-1].Gia_tri)/float(Ds_vat[i-1].Trong_luong); printf("\n\t Don gia : %.2f",Ds_vat[i-1].Don_gia); } + Sau đó dùng giải thuật sắp xếp đồ vật theo đơn giá giảm dần để xét phân nhánh. Mà đơn giá của mỗi vật sẽ bằng giá trị chia cho trọng lượng (đơn giá = giá trị/trọng lượng). Lưu đồ sắp xếp như sau: Begin l=0 end Tăng i, j lên 1 Sai Đúng i=0, j=i+1, temp[], x[] i<n ; j<n temp = gia_dv[i] gia_dv[i] = gia_dv[j] gia_dv[j] = temp l<n Đúng Sai In ten_dv, tl_dv, gt_dv, gia_dv x[l]=0 Tăng l lên 1 gt_dv[i]< gt_dv[i] Sai Code sắp xếp được viết như sau: void Sap_xep(){ Do_vat temp; for(int i=0;i<n;i++) { for (int j=i+1;j<n ;j++) { if(Ds_vat[i].Don_gia<Ds_vat[j].Don_gia) { temp=Ds_vat[i]; Ds_vat[i]=Ds_vat[j]; Ds_vat[j]=temp; } } } } - Bước 2: Nút gốc biểu diễn cho trạng thái ban đầu của ba lô, ở đó ta chưa chọn một vật nào. Tổng giá trị được chọn TGT=0, cận trên của nút gốc CT=W*Đơn giá lớn nhất - Bước 3: Nút gốc sẽ có các nút con tương ứng với các khả năng chọn đồ vật có đơn giá lớn nhất. Với mỗi nút con ta tính lại các thông số: TGT=TGT(của nút cha)+số đồ vật được chọn*giá trị mỗi vật. W=W(của nút cha) – số đồ vật được chọn * trọng lượng mỗi vật. CT=TGT+W*Đơn giá của vật sẽ xét kế tiếp. - Bước 4: Trong các nút con, ta sẽ ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn trước. Các con của nút này tương ứng với các khả năng chọn đồ vật có đơn giá lớn tiếp theo. Với mỗi nút ta lại phải xác định lại các thông số TGT, W, CT theo công thức đã nói trong bước 3. Code phân nhánh không giới hạn được viết như sau: void Phan_nhanh1(int i) { float d; d=(Balo-Weight); int t=(int)(d/Ds_vat[i].Trong_luong); for(int j=t;j>=0;j--) //xet qua tung nhanh { xtemp[i]=j; Weight= Weight+xtemp[i]*Ds_vat[i].Trong_luong; Cost= Cost+xtemp[i]*Ds_vat[i].Gia_tri; if(i==n-1) Record(xtemp); else if((Cost+Ds_vat[i+1].Don_gia*(d/Ds_vat[i+1].Trong_luong))>Best_Value) Phan_nhanh1(i+1); Weight=Weight-xtemp[i]*Ds_vat[i].Trong_luong; Cost=Cost-xtemp[i]*Ds_vat[i].Gia_tri; } } Code phân nhánh có giới hạn được viết như sau: void Phan_nhanh2(int i) { float d; d=(Balo-Weight); int a; int t=(int)(d/Ds_vat[i].Trong_luong); if(i==0) { a=(Balo/Ds_vat[i].Trong_luong); } else a=(d/Ds_vat[i].Trong_luong); if(a>Ds_vat[i].So_luong) t=Ds_vat[i].So_luong; else t=a; for(int j=t;j>=0;j--) //xet qua tung nhanh { xtemp[i]=j; if(i==0) { Weight= Ds_vat[i].Trong_luong*xtemp[i]; Cost= xtemp[i]*Ds_vat[i].Gia_tri; } else { Weight=Weight+Ds_vat[i].Trong_luong*xtemp[i]; Cost=Cost+Ds_vat[i].Gia_tri*xtemp[i]; } if(i==n-1) Record(xtemp); else if((Cost+Ds_vat[i+1].Don_gia*(d/Ds_vat[i+1].Trong_luong))>Best_Value) Phan_nhanh2(i+1); Weight=Weight-xtemp[i]*Ds_vat[i].Trong_luong; Cost=Cost-xtemp[i]*Ds_vat[i].Gia_tri; } } Trong đó Record là code ghi nhận giá trị được viết như sau: Begin i=0 end Tăng i lên 1 Sai Đúng Cost , Best, temp Cost > Best Best = Cost sl_dv[i] = temp i<n Đúng Sai void Record(int *tempVector) { int i; if(Cost > Best_Value) { Best_Value = Cost; for(i=0;i<n;i++) { x[i] = tempVector[i]; } } } - Bước 5: Lặp lại bước 4 với chú ý: đối với những nút có cận trên nhỏ hơn hoặc bằng giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì ta không cần phân nhánh cho nút đó nữa(cắt bỏ). - Bước 6: Nếu tất cả các nút đều được phân nhánh hoặc bị cắt bỏ thì phương án có giá lớn nhất là phương án cần tìm. 3. Lưu đồ khối minh họa cho phần giải thuật trên: Sắp Xếp Phân Nhánh Phân Nhánh Sắp xếp Begin Nhap Du lieu Nhập In Ket Qua In Ket Qua End 4. Bài toán ứng dụng cho phần giải thuật trên: a) Bài toán 2: (không giới hạn số lượng đồ vật) Một ba lô có trọng lượng là W=35 và 4 đồ vật được cho trong bảng sau: Loại đồ vật Giá trị Trọng lượng A 30 10 B 36 9 C 20 8 D 4 2 Giải bài toán trên dùng kỹ thuật nhánh cận. Dựa vào giải thuật vừa nêu ở trên, ta có cây phân nhánh sau: TGT = 128 W = 0 TGT = 0 W = 35 CT = 140 TGT = 108 W = 8 CT = 132 TGT = 72 W = 17 CT = 123 TGT = 36 W = 26 CT = 114 TGT = 108 W = 8 CT = 128 TGT = 0 W = 35 CT = 105 TGT = 108 W = 8 CT = 124 3B 0B 2B 1B 0A 1C 0C Ta thấy tất cả các nút trên cây đã được phân nhánh hoặc bị cắt tỉa nên phương án tốt nhất tạm thời là phương án cần tìm. Theo đó ta cần chọn 3 đồ vật loại B, 0 đồ vật loại A, 1 đồ vật loại C với tổng giá trị là:128, tổng trọng lượng là 35. b) Bài toán 3: (có giới hạn số lượng đồ vật) Một cái ba lô có trọng lượng là W = 42 và 5 loại đồ vật được cho trong bản sau: Loại đồ vật Giá trị Trọng lượng Số lượng A 30 15 2 B 25 10 3 C 2 2 2 D 6 4 2 E 24 8 2 Giải bài toán trên dùng kỹ thuật nhánh cận. Dựa vào giải thuật vừa nêu ở trên ta có cây phân nhánh: TGT = 0 W = 42 CT = 105 TGT = 0 W = 42 CT = 126 TGT=99 W=4 CT=105 TGT = 24 W = 34 CT = 109 TGT = 48 W = 26 CT = 113 TGT=49 W=24 CT=97 TGT=74 W=14 CT=102 TGT=99 W=4 CT=107 TGT=48 W=26 CT=100 TGT=73 W=16 CT=105 TGT=98 W=6 CT=104 TGT=104 W=2 TGT=98 W=6 CT=110 TGT=24 W=34 CT=72 TGT=98 W=6 CT=107 TGT=104 W=2 CT=106 TGT=106 W=0 2E 0E 1E 2B 1B 0B 3B 2B 1B 0B 0A 0A 1D 0D 1C 0C Ta thấy tất cả các nút trên cây đã được phân nhánh hoặc bị cắt tỉa nên phương án tốt nhất tạm thời là phương án cần tìm. Theo đó ta cần chọn 2 đồ vật loại E, 2 đồ vật loại B, 0 đồ vật loại A, 1 đồ vật loại D, và 1 đồ vật loại C với tổng giá trị là:106, tổng trọng lượng là 42. PHẦN III: CHƯƠNG TRÌNH DEMO HƯỚNG DẪN CÀI ĐẶT CHƯƠNG TRÌNH: - Copy thư mục VUNGOC_ANHTHO từ đĩa CD vào ổ đĩa C. - Cài đặt chương trình Bordland C++ vào ổ C (Chương trình có sẳn trong CD). Sau khi cài xong Borland C++ nhấp vào biểu tượng của chương trình ở màn hình Desktop -> File -> Open -> Chọn đường dẫn đến file VUNGOC_ANHTHO -> CTRL +F9 để chạy chương trình. - Lưu ý: Khi khởi động Borland lên, bạn vào Options -> Linker -> Libraries… -> Đánh dấu vào Graphics library để khới động thư viện đồ họa. HƯỚNG DẪN SỬ DỤNG: Đây là chương trình demo bài toán cái ba lô được giải bằng kỹ thuật nhánh cận. Ba lô có 2 dạng bài toán: ba lô có giới hạn và không có giới hạn Sau khi bấm tổ hợp phím CTRL+F9 sẽ xuất hiện giao diện như sau: Kế tiếp hãy chọn một chức năng trong menu chương trình. Nếu muốn chạy chương trình thi bấm phím 1, thoát chương trinh thi bấm phím 2. Nếu bấm phím bất kì khác với phím 1 và 2 thì chương trình lập tức sẽ thoát khỏi C. Sau đó xuất hiện thêm menu của chương trình chạy. Nếu muốn chạy chương trình bài toán ba lô không giới hạn thì bấm phím 1, ba lô có giới hạn thì bấm phím 2, và thoát chương trinh thi bấm phim 3. Nếu bấm phím bất kì khác với phím 1, 2 và 3 thì chương trình lập tức sẽ thoát khỏi C. Sau khi thực hiện các thao tác nhập dữ liệu để kiểm tra thì kết quả sẽ xuất ra như sau: Và bấm phím bất kì để trở lại menu. PHẦN IV: KẾT LUẬN I. NHẬN XÉT KẾT QUẢ ĐẠT ĐƯỢC: Sau thời gian nghiên cứu và tìm hiểu đề tài,với sự hướng dẫn tận tình của thầy cô đặc biệt giáo viên hướng dẫn thầy TRẦN PHƯỚC NGHĨA cùng sự giúp đỡ của bạn bè thì Niên Luận cơ bản đã được hoàn thành và đạt được một số kết quả như sau: Phần lý thuyết: hiểu được giải thuật đồng thời kết hợp với ngôn ngữ lập trình C để giải quyết được tương đối đầy đủ các yêu cầu đề ra. Phần demo: chương trình được thiết kế dưới dạng các chương trình con nên dễ kiểm tra và sửa lỗi. Giao diện thân thiện và dễ sử dụng, nhập dữ liệu trực tiếp trên máy. II. HẠN CHẾ: Mặc dù có cố gắng để hoàn thành Niên Luận này, nhưng bên cạnh đó vẫn còn nhiều sai xót và chưa đạt được. Phần lý thuyết: con thiếu một vài chương trình con và lưu đồ cho giải thuật. Phần demo: em chỉ viết được chương trình cho bài toán cái ba lô, chưa làm được bài toán người đi giao hàng. Em không sử dụng giao diện đồ họa nên phần giao diện của em thân thiệt với người dùng nhưng không sinh động. III. HƯỚNG PHÁT TRIỂN Cải tiến chương trình đầy đủ và hoàn thiện hơn. Phát triển chương trình sang các ngôn ngữ khác như: Turbo Pascal, Visua Basic, Java… để được hỗ trợ nhiều hơn. TÀI LIỆU THAM KHẢO [1] Giáo trình giải thuật _ Nguyễn Văn Linh _ ĐHCT. [2] Giáo trình cấu trúc dữ liệu của trường ĐHCT. [3] Giáo trình lập trình căn bản của trường ĐHBL. [4] Bài tập lập trình cơ sở _ Nhà xuất bản Giáo Dục. [5] Cấu trúc dữ liệu và giải thuật _ Nhà xuất bản Đại Học Sư Phạm.