Ví dụ về một bài toán xếp ba lô giới hạn 1 chiều: chọn các hộp nào để
làm cực đại lượng tiền trong khi giữ được tổng khối lượng dưới 15 kg?
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 các
hộp, đó là bài toán xếp vali điển hình (packing problem).
(Lời giải là chọn tất cả các hộp trừ hộp xanh lục.)
(Lời giải là chọn tất cả các hộp trừ hộp xanh lục.)
Nội dung bài toán
Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M.
Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt
giá trị cao nhất trong khả năng mà hắn có thể mang đi được.
Dạng bài toán quyết định của bài toán xếp ba lô là câu hỏi "có thể đạt được một giá trị ít nhất là bao nhiêu theo phát biểu của bài toán".Ta có n loại đồ vật, x1 tới xn. Mỗi đồ vật xj có một giá trị pj và một khối lượng wj. Khối lượng tối đa mà ta có thể mang trong ba lô là C.
Mục lục
Bài xếp ba lô 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 xếp ba lô 0-1 có thể được phát biểu bằng toán học như sau:
- Cực đại hóa
- sao cho
- Bài xếp ba lô bị chặn có thể được phát biểu bằng toán học như sau:
- Cực đại hóa
- sao cho
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
- Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng C?
- Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0?
Bài toán xếp ba lô 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 xếp ba lô tổ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 xếp ba lô đượ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.
Bài xếp ba lô 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ô)Cách giải bằng quy hoạch động
Bài toán xếp ba lô có thể được giải trong thời gian giả-đa thức bằng quy hoạch động. Dưới đây là lời giải quy hoạch động cho bài toán xếp ba lô không bị chặn.Gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Khi đó, với mỗi i ≤ C, đặt A(i) là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá i. Rõ ràng, A(C) là đáp số của bài toán.
Định nghĩa A(i) một cách đệ quy như sau:
- A(0) = 0
- A(i) = max { vj + A(i − cj),A(i) | cj ≤ i }
Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là NP-đầy đủ, do C, không như n, không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ thuận với số bit trong C, chứ không tỉ lệ với chính C.
Một giải pháp quy hoạch động tương tự cho bài toán xếp ba lô 0-1 cũng chạy trong thời gian giả-đa thức. Cũng như trên, gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Định nghĩa một hàm đệ quy A(i, j) là giá trị lớn nhất có thể đạt được với chi phí không vượt quá j và sử dụng các đồ vật trong khoảng từ x1 tới xi.
A(i,j) được định nghĩa đệ quy như sau:
- A(0, j) = 0
- A(i, 0) = 0
- A(i, j) = A(i - 1, j) if ci > j
- A(i, j) = max(A(i - 1, j), vi + A(i - 1, j - ci)) if ci ≤ j
Thuật toán tham lam
Martello và Toth (1990) đã đưa ra một thuật toán gần đúng kiểu tham lam (greedy approximation algorithm) để giải bài toán xếp ba lô. Giải thuật này sắp xếp các đồ vật theo thứ tự giảm dần về giá trị, sau đó theo thứ tự đó xếp các đồ vật vào ba lô cho đến khi không cho thêm được đồ vật nào vào nữa.Tham khảo
- Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP9, pg.247.
- Silvano Martello, Silvano; Paolo Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons. ISBN 0-471-92420-2. Đã bỏ qua văn bản “ Martello
” (trợ giúp);
- Knapsack Problems. Springer Verlag. 2005. ISBN 3-540-40286-1. Đã bỏ qua văn bản “ Kellerer
” (trợ giúp); Đã bỏ qua văn bản “ Kellerer ” (trợ giúp);|đồng tác giả=cần|tác giả=(trợ giúp)
- D. Pisinger,"Algorithms for Knapsack Problems", Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).
No comments:
Post a Comment