Trình trực quan hóa Knapsack 0/1
Quy hoạch động (dynamic programming) cho bài toán knapsack 0/1 dạng hoạt họa — điền bảng DP từng ô một, làm nổi bật các ô phụ thuộc, có điều khiển từng bước. Chạy ngay trong trình duyệt.
Mã giả
Press Run to animate the algorithm.
Time · Space
Cách dùng
- 1 Nhấn Run để điền bảng quy hoạch động từng ô một.
- 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 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 Ô ở 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
Bài toán knapsack 0/1 là gì?
Cho các món đồ, mỗi món có trọng lượng và giá trị, cùng một sức chứa W, hãy chọn một tập con (mỗi món chỉ được lấy một lần hoặc không lấy) sao cho tổng giá trị lớn nhất mà không vượt quá W.
Bảng DP hoạt động như thế nào?
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. Mỗi ô bằng max(bỏ qua món đồ = dp[i-1][w], lấy nó = dp[i-1][w-wi] + vi).
Độ phức tạp thời gian là bao nhiêu?
Thời gian O(n·W) và không gian O(n·W) (có thể giảm xuống O(W)). Đây là độ phức tạp giả đa thức (pseudo-polynomial) — hiệu quả khi W nhỏ.
Tại sao gọi là knapsack 0/1?
Mỗi món đồ hoặc được lấy trọn vẹn (1) hoặc bị bỏ qua (0) — bạn không thể lấy một phần, khác với bài toán knapsack phân số (fractional knapsack) vốn được giải bằng phương pháp tham lam (greedy).
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.
Trình trực quan hóa Knapsack 0/1 là công cụ thuật toán miễn phí của Zerethon Tools. Quy hoạch động (dynamic programming) cho bài toán knapsack 0/1 dạng hoạt họa — điền bảng DP từng ô một, làm nổi bật các ô phụ thuộc, có điều khiển từng bước. Chạy ngay trong trình duyệt. Chạy hoàn toàn trong trình duyệt — không đăng ký, không tải lên.
- Danh mục
- Thuật toán
- Giá
- Miễn phí
- Quyền riêng tư
- Chạy trên trình duyệt
- Đăng ký
- Không cần
Quyền riêng tư
Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa Knapsack 0/1 chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.
Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Dynamic Programming →
Công cụ liên quan
Trình mô phỏng Bubble Sort
Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.
Mở công cụTrình trực quan hóa Insertion Sort
Insertion Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.
Mở công cụTrình trực quan hóa Selection Sort
Selection Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.
Mở công cụTrình trực quan hóa Merge Sort
Mô phỏng merge sort có hoạt ảnh với điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt.
Mở công cụXây dựng, chia sẻ và phát triển trên Zerethon Social
Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.