Uploaded byTuấn Hoàng Show
0% found this document useful (0 votes) 416 views 39 pages Original Title4-Optimization Copyright© © All Rights Reserved Available FormatsPDF, TXT or read online from Scribd Share this documentDid you find this document useful?Is this content inappropriate?0% found this document useful (0 votes) 416 views39 pages 4 OptimizationUploaded byTuấn Hoàng Jump to Page You are on page 1of 39 Search inside document Reward Your CuriosityEverything you want to read. Anytime. Anywhere. Any device. No Commitment. Cancel anytime. 
This is a Premium Document. Some documents on Studocu are Premium. Upgrade to Premium to unlock it. Was this document helpful? This is a Premium Document. Some documents on Studocu are Premium. Upgrade to Premium to unlock it. Was this document helpful? This is a previewDo you want full access? Go Premium and unlock all pages
Bài toán tối ưu Giải bài toán cái túi sau bằng phương pháp nhánh cận, quá trình thực hiện thuật toán mô tả trên cây tìm kiếm lời giải:
5x1 + 3x2 + x3 + 4x4 11, xj N, j =1, 2, 3, 4.
7x1 + 6x2 + 4x3 + 2x4 19, xj N, j =1, 2, 3, 4.
6x1 + 5x2 + 3x3 + 2x4 17, xj N, j =1, 2, 3, 4. Giải bài toán người bán hàng với ma trận chi phí như sau: 4. 5. 6. Chú ý: Dùng cây nhị phân để lập cây tìm kiếm phương án tối ưu.
(hay còn gọi là bài toán xếp ba lô) là một bài toán tối ưu tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trong có thể nhét vừa vào một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Ví dụ về bài toán cái túi trong giới hạn một chiều: chọn các hộp nào để làm cho giá trị tiền là cực trại khi tổng trọng lượng không vượt quá 15kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của hộp, đó là bài toán xếp vali điển hình(packing problem) Ta có n loại đồ vật, từ 1 tới n. Mỗi đồ vật thứ i có trọng lượng w[i] và giá trị v[i]. Trọng lượng tối đa mà túi có thể mang được là S. 1.2 BÀI TOÁN CÁI TÚI DẠNG 0-1.Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn ) và 1 (được chọn). Bài toán cái túi bị chặn hạn chế số đồ vật huộc mỗi loại nào đó không được vượt quá một lượng nào đó. Bài cái túi không bị chặn không có một hạn chế nào về số lượng đồ vật mỗi loại. Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính chất: · là một bài toán quyết định · là một bài toán 0/1 · với mỗi đồ vật, chi phí bằng giá trị: C = V Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán cái túi khi thực ra đang có ý nói về "bài toán tổng con". Bài toán cái túi thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài cái túitổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức. Phiên bản bài toán quyết định của bài toán cái túi được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21 bài toán NP-đầy đủ của Karp. 1.3 BÀI TOÁN CÁI TÚI DẠNG PHÂN SỐVới mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô) Chương 2: Giải bài toán cái túi bằng thuật toán trực tiếp (Brute-force)Phương pháp này duyệt tất cả khả năng chất đồ vào túi, tìm cách chất có tổng giá trị lớn nhất trong số các cách chất co tổng trọng lượng các đồ vật không quá dung lượng của túi Chương 3: Giải bài toán cái túi bằng thuật toán tham lam3.1 Thực hiện bài toán này bằng thuật toán tham lamCác hàm được sử dụng : · swap (x,y) được dùng để đổi chỗ biến x và y khi sắp xếp · nhap() dùng để nhập dữ liệu từ bàn phím · sapxep() được dùng để sắp xếp lại mảng theo thứ tự giảm dần của tỉ lệ v[i]/w[i] , tức là tỉ lệ giảm dần của giá trị trên khối lượng mỗi đồ vật · thamlam() lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị trên khối lượng, biến kỉ lục ghi nhận kết quả tốt nhất khi thực hiện |
