5218 : A19 - 배낭 문제 1 (Knapsack 1)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
보물 상자에는 $N$ 개의 물건이 들어 있으며, 각 물건은 1부터 $N$ 까지 번호가 매겨져 있습니다.
물건 $i$ 의 무게는 $w_i$ 이고 가치는 $v_i$ 입니다.
타로는 몇 개의 물건을 골라 가져가려 합니다. 하지만 그의 배낭에는 무게 제한이 있어, 무게의 합이 $W$ 이하가 되도록 해야 합니다.
얻을 수 있는 가치의 합의 최댓값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 100$
• $1 \le W \le 100000$
• $1 \le w_i \le W$
• $1 \le v_i \le 10^9$
• 입력되는 모든 값은 정수입니다.
물건 $i$ 의 무게는 $w_i$ 이고 가치는 $v_i$ 입니다.
타로는 몇 개의 물건을 골라 가져가려 합니다. 하지만 그의 배낭에는 무게 제한이 있어, 무게의 합이 $W$ 이하가 되도록 해야 합니다.
얻을 수 있는 가치의 합의 최댓값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 100$
• $1 \le W \le 100000$
• $1 \le w_i \le W$
• $1 \le v_i \le 10^9$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$ 과 $W$ 가 공백으로 구분되어 주어집니다.
다음 $N$ 개 줄에 각 물건의 무게 $w_i$ 와 가치 $v_i$ 가 공백으로 구분되어 주어집니다.
다음 $N$ 개 줄에 각 물건의 무게 $w_i$ 와 가치 $v_i$ 가 공백으로 구분되어 주어집니다.
출력 설명
얻을 수 있는 가치의 합의 최댓값을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 7
3 13
3 17
5 29
1 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
40