Bạn đang xem: Hướng dẫn giải bài toán cái túi
3. Một số trong những ví dụ minh họa
3.4. Việc cái túi
Bài toán 3.4. Mang lại n dụng cụ (n ≤ 100), đồ vật thứ i tất cả trọng lượng là wi (wi ≤ 100) và có giá trị thực hiện là ci (ci ≤ 100). Buộc phải xếp đồ vật vào một chiếc túi sao để cho tổng giá bán trị sử dụng được xếp vào trong túi là bự nhất. Biết rằng cái túi chỉ hoàn toàn có thể mang được trọng lượng không vượt thừa b (b ≤ 100).
a) Phương pháp qui hoạch động
Bước 1. Nêu giảđịnh về hàm qui hoạch hễ
Gọi f(i, j) là cực hiếm sử dụng lớn số 1 của của những đồ đồ dùng được xếp vào túi khi chọn các đồ thứ 1, 2, …, i với trọng lượng số lượng giới hạn của túi là j. Khi đó giá trị nghiệm cực tốt của việc là f(n, m).
Bước 2:Tìm nghiệm của các bài toán con đơn giản dễ dàng
Dễ thấy f(0, j) = 0 với mọi j = 1, 2, …, b
Bước 3: Xây dựng công thức qui hoạch động
Với số lượng giới hạn trọng lượng j, việc chọn tối ưu trong các đồ đồ vật 1, 2, …, i - 1, i để sở hữu giá trị lớn nhất có nhị khả năng:
• còn nếu như không chọn dụng cụ thứ i thì f(i, j) là cực hiếm sử dụng lớn số 1 có thể bằng cách chọn trong số đồ đồ dùng 1, 2, …, i - 1 với trọng lượng j, tức là
f(i, j) = f (i-1, j)
• Nếu có chọn dụng cụ i (với wi ≤ j) thì f(i, j) bởi giá trị thực hiện của dụng cụ thứ i cộng với giá trị áp dụng lớn nhất rất có thể được bằng phương pháp chọn trong các các gói 1, 2, …, i - 1 với giới hạn trọng lượng là j - wi. Nói cách khác ta bao gồm công thức:
f(i, j) = ci + f(i-1, j - wi)
Kết phù hợp hai kĩ năng trên ta có công thức qui hoạch động: f(i, j) = max f(i-1, j) , ci + f(i-1, j - wi) cùng với i = 1, 2, …, n với j = 0, 1, 2, .., M.
Bước 4. Tra cứu lại nghiệm
Ta đồng điệu hàm f(i,j) cùng với bảng F<1..n, 1..b> (còn điện thoại tư vấn là bảng qui hoạch động). Sau khoản thời gian tính xong mảng F, việc truy lốt trên F để tìm nghiệm như sau:
Chú ý rằng F
Nếu F
b) mô phỏng Pascal procedure Caitui; begin for j := 0 khổng lồ b bởi F<0, j> := 0; for i := 1 to lớn n vày for j := 1 khổng lồ b bởi begin F
if (j > wi) and (F
end; end; procedure Trace; begin write(‘Max value: ‘, F
write(‘Chon bởi vì vat ‘, n, ‘ w = ‘, wn, ‘ value = ‘, vn); b := b - wn;
end; n := n - 1; end;
một trong những phần của tài liệu
Bạn đang xem văn bản tài liệu Đề tài câu hỏi cái túi, để download tài liệu về máy các bạn click vào nút tải về ở trên
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘIViện công nghệ Thông tin và Truyền thông
BÀI TẬP LỚN MÔN HỌC THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁNĐề tài: BÀI TOÁN CÁI TÚI học viên thực hiện: 1. Đào Duy Thành. SHHV:20082364 Mã lớp: 29106Giáo viên phía dẫn: PGS Nguyễn Đức Nghĩa
HÀ NỘI – 2011Mục lục
Giới thiệu :Báo cáo này sẽ trình diễn về các thuật toán giải quyết và xử lý bài toán dòng túi. Trong những số đó có sử dụng 2 giải mã là: giải mã tham lam (Greedy) cùng Quy hoạch rượu cồn (Dynamic progaming). Trường đoản cú đó đưa ra các reviews về độ phức tạp của thuật toán và chọn lọc phương án buổi tối ưu.Xin thực bụng cám ơn thầy Nguyễn Đức Nghĩa đã giúp sức em triển khai bài toán này
Hà Nội mon 12 năm 2011Chương I : việc cái túi
Giới thiệu.Bài toán cái túi (hay còn gọi là bài toán xếp tía lô) là 1 trong những bài toán về tối ưu tổ hợp. Bài bác toán được lấy tên từ vụ việc chọn rất nhiều gì quan trong hoàn toàn 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 vào một chuyến đi.Nội dung vấn đề như sau: Một kẻ trộm bỗng dưng nhập vào trong 1 cửa hiệu kiếm tìm thấy gồm n sản phẩm có trọng lượng và cực hiếm khác nhau, mà lại hắn chỉ mang theo một cái túi gồm sức cất về trọng lượng tối đa là M. Vậy kẻ trộm đề nghị bỏ vào túi phần đa món như thế nào và con số bao nhiêu nhằm đạt giá chỉ trị cao nhất trong năng lực mà hắn hoàn toàn có thể mang đi được.Ví dụ về việc cái túi trong số lượng giới hạn một chiều: chọn những hộp nào để triển khai cho quý giá tiền là rất trại khi tổng trọng lượng ko vượt thừa 15kg? vấn đề đa chiều hoàn toàn có thể xét đến cân nặng riêng và form size của hộp, đó là câu hỏi xếp vali điển hình(packing problem)Ta bao gồm n loại đồ vật, từ là 1 tới n. Mỗi đồ vật thứ i tất cả trọng lượng w và quý giá v. Trọng lượng về tối đa nhưng mà túi rất có thể mang được là S.Bài toán chiếc 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ới 1 (được chọn).Bài toán chiếc túi hoàn toàn có thể được phạt biểu bởi toán học như sau:Cực đại hóa sao cho với hoặc 1Bài toán dòng túi bị chặn tinh giảm số đồ vật huộc mỗi nhiều loại nào kia không được vượt quá một lượng như thế nào đó.Có thể được phân phát biểu bởi toán học tập như sau
Cực đại hóa làm thế nào để cho với bài xích cái túi không xẩy ra chặn không có một hạn chế nào về số lượng đồ trang bị mỗi loại.Một trường hợp đặc biệt của vấn đề này nhận được rất nhiều quan tâm, đó là vấn đề với các tính chất:là một câu hỏi quyết địnhlà một bài toán 0/1với mỗi trang bị vật, chi tiêu bằng giá bán trị: C = VTrường hợp đặc biệt này được gọi là câu hỏi tổng những tập con (subset sum problem). Với một số trong những lý do, trong lĩnh vực mật mã học, fan ta hay được sử dụng cụm từ bỏ "bài toán cái túi khi thực ra đang có ý nói đến "bài toán tổng con".Bài toán dòng túi thường xuyên được giải bằng quy hoạch động, tuy chưa tồn tại một thuật toán thời hạn đa thức cho vấn đề tổng quát. Cả bài cái túitổng quát mắng và việc tổng bé đều là những bài NP-khó, và điều đó dẫn mang đến các cố gắng sử dụng tổng bé làm cửa hàng cho các khối hệ thống mật mã hóa khóa công khai, ví dụ điển hình Merkle-Hellman. Các cố gắng này hay được sử dụng nhóm thế vì những số nguyên. Merkle-Hellman và một số thuật toán tựa như khác đã bị phá, do những bài toán tổng con ví dụ mà họ tạo nên thực ra lại giải được bằng những thuật toán thời hạn đa thức.Phiên bản bài toán đưa ra quyết định của câu hỏi cái túi được diễn đạt ở trên là NP-đầy đủ cùng trong thực tế là 1 trong các 21 việc NP-đầy đủ của Karp.Bài toán chiếc túi dạng phân số
Với từng loại, rất có thể chọn một phần của nó (ví dụ: 1Kg bơ hoàn toàn có thể được giảm ra thành đa số để vứt vào ba lô)Chương 2: Giải bài toán cái túi bởi thuật toán trực tiếp (Brute-force)Phương pháp này chăm bẵm tất cả khả năng chất đồ vật vào túi, tìm bí quyết chất có tổng mức lớn nhất trong số các giải pháp chất teo tổng trọng lượng các đồ đồ vật không quá dung lượng của túi
Tuy nhiên, phương thức này không nhiều được sử dụng do gồm độ phức tạp O (n2)Chương 3: Giải bài toán cái túi bởi thuật toán tham lam3.1 Greedy 1Giải thuật: chuẩn bị xếp những đồ đồ dùng theo lắp thêm tự ko tăng của giá chỉ trị.Lần lượt xét các đồ đồ theo lắp thêm tự đã sắp tới , và hóa học đồ vẫn xét vào túi ví như như dung tích còn lại của loại túi đó đủ cất nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của các đồ vật vẫn xét không vượt quá năng lực của túi).Tuy nhiên, phương pháp này chưa cho giải mã chính xác3.2 Greedy 2Sắp xếp các đồ thiết bị theo thiết bị tự không bớt của trọng lượng
Lần lượt xét những đồ thứ theo vật dụng tự đã sắp tới , và chất đồ sẽ xét vào túi giả dụ như dung lượng còn lại của chiếc túi đủ đựng nó (tức là tổng trọng lượng của các đồ vật sẽ xếp vào túi cùng trọng lượng của các đồ vật đã xét không vượt quá dung tích của túi).Tương từ Greedy 1, cách thức này chưa mang lại được độ đúng mực cần thiết3.3 Greedy 3Sắp xếp các đồ trang bị theo vật dụng tự không tăng của quý hiếm một đơn vị chức năng trọng lượng () thứu tự xét những đồ trang bị theo vật dụng tự sẽ sắp, và chất đồ vật đang xét vào túi giả dụ như dung lượng còn lại của cái túi đủ đựng nó3.4 Greedy 4Gọi là giải mã thu được theo thuật toán Greedy j , j=1;2;3 gọi là lời giải đạt
Định lý: Lời giải vừa lòng đẳng thức3.5 triển khai bài toán loại túi theo Greedy 3 bằng C++Các hàm được sử dụng :swap (x,y) được dùng để làm đổi chỗ thay đổi x với y khi chuẩn bị xếpnhap() dùng làm nhập dữ liệu từ bàn phímsapxep() được dùng để làm sắp xếp lại mảng theo trang bị tự bớt dần của tỉ trọng v/w , tức là tỉ lệ sút dần của quý giá trên trọng lượng mỗi thiết bị vậtthamlam() theo thứ tự trọn các đồ vật đang được sắp xếp theo trang bị tự sút dần của giá trị trên khối lượng, trở nên kỉ lục ghi nhận hiệu quả tốt nhất lúc thực hiện
Độ phức tạp:Nếu thực hiện sắp xếp dễ dàng và đơn giản (chèn, nổi bọt…) thì độ tinh vi của cả việc là O(n2)Nếu thực hiện quick sort hoặc merge sort thì độ phức hợp là O(nlogn) giỏi hơn so với giải trực tiếp
Giao diện nhập số liêu
Kết quả thu được
Chương IV: Giải việc cái túi bởi thuật toán quy hướng động.4.1 mô tả:Với mỗi và , xét câu hỏi . Tính là tổng mức lớn nhất của những đồ vật dụng được chọn trong các k đồ vật thứ nhất và gồm tổng trọng lượng không thực sự S.Có tất cả bài toán. Việc cần giải là giá chỉ trị tối ưu đề nghị tìm là với k=1 ta bao gồm Gỉa sử tính được với đa số và . Khi đó, để tính ta có thể lập luận như sau
Nếu thì dụng cụ thứ k tất yêu chất vào túi, cho nên vì vậy cách chất buổi tối ưu chỉ rất có thể sử dụng k-1 đồ vật trước đó và có giá trị là ví như thì phương pháp chất buổi tối ưu đề nghị lựa lựa chọn trong 2 biện pháp chất sau
Không chất đồ vật k vào túi, khi ấy giá trị của phương pháp chất tối ưu đã là Chất đồ vật hứ k vào túi, lúc đó trọng lượng còn lại sẽ được chất buổi tối ưu từ vật vật đầu tiên với giá bán trị buổi tối ưu vẫn là Từ đó ta có công thức đệ quy4.2 thừa nhận xét:Thuật toán giải việc cái túi tất cả thời gian review là O(n
L). Thời hạn này phụ thuộc vào tuyến tính vào tài liệu vào L, nhưng nếu xét nó như là hàm của độ dài tài liệu vào , thì sự dựa vào này lại là hàm mũ.Trên thực tế,thuật toán này có tác dụng việc kết quả khi L ko là thừa lớn
Xem thêm: Hướng Dẫn Làm Cv Online Chuẩn Nhất, Tạo Cv Online Miễn Phí
Tài liệu tìm hiểu thêm chính:Nguyễn Đức Nghĩa. Bài xích giảng kiến thiết và đối chiếu thuật toán. ĐHBK Hà nội, 2010.Wikipedia.org và các nguồn không giống từ internet