Trình trực quan hóa Knapsack 0/1

Cách dùng

1. 1 Nhấn Run để điền bảng quy hoạch động từng ô một.
2. 2 Mỗi hàng là một món đồ; mỗi cột là một sức chứa từ 0 đến W.
3. 3 Mỗi ô là giá trị tốt nhất giữa việc bỏ qua món đồ (ô màu xanh phía trên) hoặc lấy nó.
4. 4 Ô ở góc dưới cùng bên phải là giá trị tốt nhất có thể đạt được. Nhấn Shuffle để có bộ món đồ mới.

Vì sao dùng công cụ này

• Xem bài toán knapsack 0/1 được giải bằng quy hoạch động, thay vì vét cạn (brute force).
• Quan sát từng ô được xây dựng từ hai ô mà nó phụ thuộc vào.
• Hiểu thời gian chạy O(n·W) so với vét cạn có độ phức tạp hàm mũ.
• Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không tải lên.

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

Trình trực quan hóa Knapsack 0/1 là gì?

Trình trực quan hóa Knapsack 0/1 mô phỏng hoạt họa bảng quy hoạch động, trong đó dp[i][w] là giá trị tốt nhất khi dùng i món đồ đầu tiên với sức chứa w, được tính bằng max giữa bỏ qua hoặc lấy từng món đồ. Ô ở góc dưới cùng bên phải là giá trị tối ưu.

Tính năng

Ví dụ

items (w,v) = (10,60),(20,100),(30,120); capacity 50

max value = 220 (take items 2 and 3, weight 50)

Trường hợp sử dụng

1. 1

   Học quy hoạch động

   Xem cách các bài toán con chồng lấp xây dựng nên giá trị tối ưu.

2. 2

   Phân bổ tài nguyên

   Mô hình hóa việc chọn vật phẩm dưới giới hạn trọng lượng hoặc ngân sách.

3. 3

   Hiểu về giả đa thức

   Hiểu tại sao O(nW) không thực sự là đa thức.

Tài liệu tham khảo

• Bài toán knapsack — Wikipedia
• MIT OCW 6.006 — Introduction to Algorithms (CLRS) — MIT OpenCourseWare

Công cụ liên quan