5029 : 배낭 문제 1
•시간제한: 2.000 S
•메모리제한: 512 MB
•제출: 8
•통과: 2
•만든사람: suakii
문제 설명
$N$ 개의 물건이 있습니다. $i$ 번째 물건의 무게는 $w_i$, 가치는 $v_i$ 입니다. 무게의 총합이 $W$ 를 넘지 않도록 물건을 선택할 때, 가치의 총합의 최댓값을 구하십시오.
[제약 조건]
• 입력되는 모든 값은 정수입니다.
• $1 \le N \le 100$
• $1 \le W \le 10^5$
• $1 \le w_i \le W$
• $1 \le v_i \le 10^9$
입력 설명
첫째 줄에 $N$ 과 $W$ 가 주어집니다.
이후 $N$ 개 줄에 $w_i, v_i$ 가 주어집니다.
출력 설명
가치 총합의 최댓값을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 8
3 30
4 50
5 60
출력 예시
COPY
복사되었습니다!
복사되었습니다!
90