Ba lô 0/1 với sức chứa nhỏ
Ba lô 0/1 là bài quy hoạch động kinh điển thứ hai sau bài leo cầu thang. Mỗi món đồ chỉ có
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Ba lô 0/1 là bài quy hoạch động kinh điển thứ hai sau bài leo cầu thang. Mỗi món đồ chỉ có một bản, nên ta hoặc lấy trọn nó hoặc bỏ qua, không có chuyện lấy một nửa. Chính ràng buộc "mỗi món một lần" quyết định chiều chạy của vòng lặp trong.
Yêu cầu
Có n món đồ, món thứ i nặng wi và có giá trị vi. Ba lô chịu được tổng khối lượng tối đa W. Hãy chọn một tập con các món sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. In ra tổng giá trị lớn nhất đó.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: hai số nguyên n và W (1 <= n <= 50, 1 <= W <= 100).
- n dòng tiếp theo, dòng thứ i chứa hai số nguyên wi và vi
(1 <= wi <= 100, 0 <= vi <= 1000).
Output
- Một số nguyên trên một dòng là tổng giá trị lớn nhất chọn được. In 0 nếu không món nào
vừa ba lô.
Ràng buộc
- Mỗi món chỉ được chọn tối đa một lần.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3 10
5 10
4 40
6 30
Output
70
Ví dụ 2
Input
2 5
2 3
3 4
Output
7
Giải thích
Lấy món nặng 4 (giá trị 40) và món nặng 6 (giá trị 30), tổng khối lượng đúng 10 và tổng giá trị 70. In ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
