Bài toán cái túi

Một người leo núi có giới hạn trọng lượng, một tên trộm với chiếc bao, một công ty với ngân sách và danh sách dự án: tất cả đều gặp cùng một câu hỏi. Nên cho những gì vào để được nhiều giá trị nhất mà không vượt quá giới hạn? Đó là bài toán cái túi, và quy hoạch động giải nó chính xác khi các trọng lượng là số nguyên có độ lớn vừa phải.

Một bảng với các hàng đồ vật và các cột sức chứa, đường truy ngược màu cam, bên cạnh là một chiếc túi và các đồ vật nhiều kích cỡ
Một bảng với các hàng đồ vật và các cột sức chứa, đường truy ngược màu cam, bên cạnh là một chiếc túi và các đồ vật nhiều kích cỡ

Bài toán

Có n đồ vật, mỗi đồ vật có một trọng lượng và một giá trị, và một chiếc túi chứa được tối đa trọng lượng W. Hãy chọn một tập đồ vật có tổng trọng lượng không quá W và tổng giá trị lớn nhất có thể. Mỗi đồ vật hoặc được xếp nguyên vẹn, hoặc ở ngoài, vì vậy nó được gọi là bài toán cái túi 0/1. Với n đồ vật có 2ⁿ tập có thể, nên thử hết chúng sớm trở nên bất khả thi.

Bảng

Gọi best[i][w] là giá trị lớn nhất có thể xếp vừa trọng lượng w khi chỉ dùng i đồ vật đầu tiên. Khi đó best[0][w] = 0, và với mỗi hàng sau có hai lựa chọn: bỏ đồ vật i ra, được best[i − 1][w], hoặc nếu trọng lượng wᵢ của nó vừa, xếp nó vào, được giá trị của nó cộng với best[i − 1][w − wᵢ]. Giá trị lớn hơn là best[i][w]. Điền bảng theo từng hàng giúp hai ô cần dùng luôn có sẵn.

Một ví dụ

Lấy sức chứa 7 và bốn đồ vật có trọng lượng 1, 3, 4 và 5 với giá trị 1, 4, 5 và 7. Chỉ với đồ vật thứ nhất, mọi sức chứa từ 1 trở lên đều có giá trị 1. Thêm đồ vật thứ hai, sức chứa 4 chứa được cả hai với giá trị 5. Thêm đồ vật thứ ba, sức chứa 7 chứa được đồ vật 2 và 3 với giá trị 9. Đồ vật thứ tư, nặng 5 và có giá trị 7, có thể đi cùng đồ vật 1 được 8 ở sức chứa 6 hoặc 7, nhưng 9 tốt hơn, nên ô dưới cùng bên phải là 9: xếp các đồ vật nặng 3 và 4.

Khó đến mức nào?

Bảng cần khoảng n·W bước. Trông có vẻ nhanh, nhưng W là một con số, và một số có d chữ số có thể lớn tới 10 mũ d, nên công việc tăng theo hàm mũ với độ dài đầu vào. Bài toán cái túi là NP-khó; nó là một trong 21 bài toán NP-đầy đủ của Richard Karp năm 1972. Trong thực tế, phương pháp bảng, nhánh và cận, cùng các lược đồ xấp xỉ tốt xử lý tốt những trường hợp thực tế lớn.

Lịch sử và ứng dụng

Cái tên này bắt nguồn từ nhà toán học Tobias Dantzig vào đầu thế kỷ 20, và con trai ông là George Dantzig đã đưa ra một phương pháp tham lam kinh điển cho nó vào năm 1957. Bài toán cái túi xuất hiện trong lập ngân sách và chọn danh mục đầu tư, trong cắt nguyên liệu thô sao cho ít hao hụt nhất, trong xếp hàng hóa, và cả trong mật mã khóa công khai thời kỳ đầu: hệ mật Merkle–Hellman năm 1978 được xây dựng dựa trên một bài toán cái túi, và bị phá vài năm sau đó.

George Dantzig (trái) nhận National Medal of Science từ Tổng thống Gerald Ford năm 1976. Năm 1957 Dantzig đưa ra một phương pháp tham lam cổ điển cho bài toán cái ba lô. Bản thân cái tên bắt nguồn từ cha ông, Tobias Dantzig.
George Dantzig (trái) nhận National Medal of Science từ Tổng thống Gerald Ford năm 1976. Năm 1957 Dantzig đưa ra một phương pháp tham lam cổ điển cho bài toán cái ba lô. Bản thân cái tên bắt nguồn từ cha ông, Tobias Dantzig.

Tự khám phá

Mở ứng dụng, chuyển sang chế độ xem Bảng và nhấn Bước. Ô màu cam là ô đang được điền, còn các ô màu xanh là hai ô mà nó so sánh: ô ngay phía trên, và ở hàng trên, ô lùi sang trái đúng bằng trọng lượng của đồ vật. Sau ô cuối cùng, quá trình truy ngược đi lên từ góc dưới bên phải bằng màu cam, và các đồ vật đã xếp hiện ra bên dưới bảng.

Câu hỏi thường gặp

Cái túi 0/1, có giới hạn và không giới hạn khác nhau thế nào?

Trong phiên bản 0/1, mỗi đồ vật được lấy nhiều nhất một lần. Trong phiên bản có giới hạn, mỗi đồ vật có một số bản sao giới hạn, còn trong phiên bản không giới hạn thì bao nhiêu cũng được. Bảng chỉ thay đổi một chút giữa các phiên bản.

Phương pháp tham lam có bao giờ đúng với bài toán cái túi không?

Với bài toán cái túi phân số, khi đồ vật có thể chia nhỏ, lấy trước thứ có giá trị trên trọng lượng cao nhất là tối ưu. Với đồ vật nguyên vẹn, kết quả có thể sai lệch nhiều, dù kết quả tốt hơn giữa phương pháp tham lam và một đồ vật giá trị nhất luôn đạt ít nhất một nửa giá trị tốt nhất.

Bảng cần bao nhiêu bộ nhớ?

(n + 1)·(W + 1) ô cho bảng đầy đủ, đó là thứ bạn cần để truy ngược các đồ vật. Nếu chỉ cần giá trị tốt nhất, một hàng gồm W + 1 ô là đủ, điền từ phải sang trái.

Bài toán cái túi có giống bài toán tổng tập con không?

Tổng tập con là trường hợp đặc biệt trong đó giá trị của mỗi đồ vật bằng trọng lượng của nó và câu hỏi là liệu có thể xếp đầy túi một cách chính xác hay không. Nó cũng là NP-đầy đủ và được giải bằng cùng một loại bảng.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử bài toán cái túi