7198 : 조합 최적화
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
배낭의 최대 무게 제한 W와 N개의 물건들의 무게, 가치가 주어집니다. 배낭에 담을 수 있는 물건들의 가치 합의 최댓값을 구하는 배낭 문제(Knapsack)를 해결하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 물건의 개수 N과 배낭의 가용 무게 W가 주어집니다. (1 ≤ N ≤ 20, W는 자연수)
둘째 줄부터 N개의 줄에 각 물건의 무게와 가치가 주어집니다.
둘째 줄부터 N개의 줄에 각 물건의 무게와 가치가 주어집니다.
출력 설명
배낭에 담을 수 있는 최대 가치 합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 8
2 4
3 0
2 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
16도움
무게 1(가치 8), 무게 2(가치 4) 두 개를 선택하여 무게 합 5 이하에서 최대 가치 16을 얻을 수 있습니다. (1(8) + 2(4) + 2(4) = 16)