💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Lấp Đầy Ba Lô
EXACTPACK
## Đề bài Có `n` vật. Vật thứ `i` có khối lượng `wi` và giá trị `vi`. Cần chọn một số vật sao cho tổng khối lượng đúng bằng `W`. Mỗi vật được chọn tối đa một lần. Trong các cách chọn có tổng khối lượng đúng bằng `W`, hãy tìm tổng giá trị lớn nhất. Nếu không có cách nào, in ra `-1`. ## 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 tổng giá trị lớn nhất nếu có thể lấp đầy đúng `W`, ngược lại in `-1`. ## 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 ≤ 20000` | 30% | | 3 | Không có ràng buộc bổ sung | 40% | ## Ví dụ ### Input ```text 4 10 6 12 3 5 4 7 2 4 ``` ### Output ```text 19 ``` ### Giải thích Chọn vật có khối lượng `6` và `4`, tổng khối lượng đúng `10`, tổng giá trị `12 + 7 = 19`.
✅ Đã AC: 2 / 4 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