💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Ba Lô 0-1
KNP01
## Đề bài Có `n` vật. Vật thứ `i` có khối lượng `wi` và giá trị `vi`. Một chiếc ba lô có sức chứa tối đa `W`. Mỗi vật chỉ được chọn tối đa một lần. Hãy tìm tổng giá trị lớn nhất có thể đạt được sao cho tổng khối lượng các vật được chọn không vượt quá `W`. ## Dữ liệu vào Dòng 1 chứa hai số nguyên `n, W`. `n` dòng tiếp theo, dòng thứ `i` chứa hai số nguyên `wi, vi`. ## Dữ liệu ra In ra một số nguyên duy nhất là tổng giá trị lớn nhất. ## Giới hạn - `1 ≤ n ≤ 200` - `1 ≤ W ≤ 200000` - `1 ≤ wi ≤ 10^9` - `1 ≤ vi ≤ 10^9` ## Phân loại subtask | Subtask | Ràng buộc | Điểm | | --- | --- | --- | | 1 | `n ≤ 25`, `W ≤ 500` | 30% | | 2 | `n ≤ 100`, `W ≤ 10000` | 30% | | 3 | Không có ràng buộc bổ sung | 40% | ## Ví dụ ### Input ```text 3 5 2 3 3 4 4 5 ``` ### Output ```text 7 ``` ### Giải thích Chọn vật 1 và vật 2, tổng khối lượng `2 + 3 = 5`, tổng giá trị `3 + 4 = 7`.
✅ Đã AC: 5 / 12 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng