- Đang điền
- Được đọc
- Đáp án
Bài toán cái túi
Bạn chỉ mang được một trọng lượng có hạn, và mỗi đồ vật đều có trọng lượng và giá trị. Nên lấy những đồ vật nào để mang được nhiều giá trị nhất? Thử mọi tổ hợp thì công việc tăng gấp đôi với mỗi đồ vật. Một bảng với các hàng là đồ vật và các cột là sức chứa sẽ tìm ra cách xếp túi tốt nhất, từng ô một. Chạm vào một đồ vật để xếp nó vào túi, và chạm lại (trong túi hoặc trên kệ) để lấy nó ra. Túi đầy dần theo trọng lượng, và các ô thông tin cho thấy số đô la bạn đã xếp so với mức tốt nhất có thể. Nhấn Xếp tốt nhất để xem túi tốt nhất. Trong khung điều khiển, hãy thay đổi số ký và số đô la của các đồ vật, thêm hoặc xóa đồ vật, và đặt sức chứa của túi. Chế độ xem Bảng cho thấy quy hoạch động tìm ra túi tốt nhất như thế nào: nhấn Phát để xem bảng được điền dần, hoặc Bước và Lùi để đi từng bước một, và kéo thanh trượt bước để nhảy đến bất kỳ đâu. Mỗi hàng thêm một đồ vật, mỗi cột là một sức chứa tính bằng ký, và mỗi ô chứa số đô la nhiều nhất có thể xếp vừa. Khi bảng đang được chọn, các phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chạm vào các hộp đồ vật để xếp chúng vào túi, và xem túi đầy dần theo khối lượng tính bằng kilôgam.
- Hãy cố đạt giá trị cao nhất có thể tính bằng đô la, hoặc nhấn Xếp tốt nhất để xem cách xếp tốt nhất.
- Mở chế độ xem Bảng và nhấn Phát để xem mỗi ô chọn giữa xếp và bỏ lại một đồ vật.
Bảng hoạt động thế nào
Mỗi hàng thêm một đồ vật và mỗi cột là một sức chứa, từ 0 đến sức chứa của túi. Một ô giữ giá trị lớn nhất có thể xếp vừa sức chứa đó khi dùng các đồ vật tính đến hàng của nó. Nếu không có đồ vật mới, đó là ô phía trên. Nếu có đồ vật mới và nó vừa, đó là giá trị của đồ vật cộng với giá trị tốt nhất cho phần trọng lượng còn lại, nằm ở hàng trên, lùi sang trái đúng bằng trọng lượng của đồ vật. Ô giữ giá trị lớn hơn trong hai giá trị đó. Hàng đầu tiên, chưa có đồ vật nào, toàn là số 0.
Truy ngược các đồ vật
Ô dưới cùng bên phải là giá trị tốt nhất. Để tìm các đồ vật, bắt đầu từ đó và so sánh với ô phía trên: nếu bằng nhau, đồ vật cuối không cần đến; nếu lớn hơn, đồ vật đó nằm trong túi, vậy trừ đi trọng lượng của nó và chuyển sang cột đó. Mỗi lần đi lên một hàng cho đến hàng đầu tiên. Ứng dụng hiển thị quá trình truy ngược này bằng màu cam và liệt kê các đồ vật đã xếp bên dưới bảng.
Câu hỏi thường gặp
0/1 trong bài toán cái túi 0/1 nghĩa là gì?
Mỗi đồ vật được xếp một lần hoặc không xếp, không bao giờ xếp một phần và không bao giờ xếp hai lần. Nếu đồ vật có thể cắt nhỏ, như hạt gạo, thì xếp trước những thứ có giá trị trên mỗi đơn vị trọng lượng cao nhất sẽ là tối ưu; đó là bài toán cái túi phân số.
Sao không xếp trước đồ vật có giá trị trên trọng lượng cao nhất?
Vì đồ vật nguyên vẹn có thể để lại chỗ trống. Với sức chứa 7 và các đồ vật nặng 1, 3, 4 và 5 có giá trị 1, 4, 5 và 7, đồ vật có giá trị trên trọng lượng cao nhất là đồ vật nặng 5, và nó chỉ để lại chỗ cho đồ vật nặng 1, tổng cộng 8. Hai đồ vật nặng 3 và 4 cộng lại có giá trị 9.
Thuật toán cái túi nhanh đến mức nào?
Bảng có (số đồ vật + 1) nhân (sức chứa + 1) ô, mỗi ô được điền trong một bước. Như vậy là nhanh với sức chứa nhỏ, nhưng sức chứa có thể là một số rất lớn, nên nói chung bài toán là NP-khó; phương pháp bảng này được gọi là giả đa thức.
Một đồ vật có thể được xếp hai lần không?
Ở đây thì không. Trong bài toán cái túi không giới hạn, mỗi đồ vật có thể được lấy bao nhiêu lần cũng được; khi đó bảng đọc ô bên trái trong cùng hàng thay vì hàng trên, giống như trong ứng dụng đổi tiền xu.
Có dữ liệu nào được gửi đi không?
Không. Mọi thứ đều được tính trong trình duyệt của bạn, và các thiết lập gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa