0202- Luyện thi cấp tốc

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 250M
Input: stdin
Output: stdout

Author:
Problem type

Luyện Thi Cấp Tốc (Dạng Knapsack)
Phát biểu bài toán: Kỳ thi cuối kỳ sắp đến, Minh chỉ còn đúng T giờ để ôn tập. Có N chuyên đề kiến thức cần phải ôn. Với mỗi chuyên đề thứ i, Minh biết rằng cần time[i] giờ để học và nếu học xong sẽ chắc chắn được point[i] điểm trong bài thi.
Vì thời gian có hạn, Minh không thể ôn hết tất cả các chuyên đề. Với mỗi chuyên đề, Minh chỉ có thể chọn học hoặc không học (không thể học một nửa). Hãy giúp Minh lên kế hoạch ôn tập để đạt được tổng số điểm cao nhất có thể.


Input:
• Dòng đầu tiên chứa hai số nguyên N và T (1 ≤ N ≤ 100, 1 ≤ T ≤ 1000).
• N dòng tiếp theo, mỗi dòng chứa hai số nguyên time[i] và point[i] (1 ≤ time[i], point[i] ≤ 1000).
Output:
• Một số nguyên duy nhất là tổng số điểm tối đa Minh có thể đạt được.


Ví dụ:
Input:
4 10
5 8
4 5
6 9
3 4
Output:
13
Giải thích:
 Minh có thể chọn ôn chuyên đề 1 (5 giờ, 8 điểm) và chuyên đề 4 (3 giờ, 4 điểm). Tổng thời gian là 8 giờ (≤ 10) và tổng điểm là 12 điểm.
 Một lựa chọn tốt hơn là ôn chuyên đề 1 (5 giờ, 8 điểm) và chuyên đề 2 (4 giờ, 5 điểm), tổng thời gian 9 giờ, tổng điểm 13.


Comments

There are no comments at the moment.