5318 : B19 - 배낭 문제 2
•시간제한: 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 10^9$
• $1 \le w_i \le W$
• $1 \le v_i \le 1000$
• 입력되는 모든 값은 정수입니다.
타로 군은 몇 개의 물건을 골라 가져가고 싶어 합니다. 하지만 배낭의 용량 제한이 있어 무게의 합계가 $ W $ 이내가 되도록 해야 합니다.
가치 합계로 가능한 최대값은 얼마입니까?
[제약 조건]
• $1 \le N \le 100$
• $1 \le W \le 10^9$
• $1 \le w_i \le W$
• $1 \le v_i \le 1000$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫 번째 줄에 $ 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