1825: 0/1 배낭 문제(S)
[만든사람 : onthebitLab-admin 2022/12/21]
문제 설명
어떤 배낭에 W무게만큼 물건을 담을 수 있다.
물건들은 (무게 wi, 가격 vi) 정보를 가지고 있는데, 물건들을 조합해서 담아 가격
의 총합이 최대가 되게 하려고 한다.
** 물건들은 한 종류씩 밖에 없으며, 절대 배낭의 무게를 초과해서는 안 된다. **
** 물건들은 한 종류씩 밖에 없으며, 절대 배낭의 무게를 초과해서는 안 된다. **
입력 설명
첫째 줄에 물건의 개수 n(1<= n <= 100)과 배낭의 무게 w(1 <= w <= 10000)가
입력된다.
둘째 줄부터 n+1째줄 까지 물건들의 정보가 wi, vi가 한 줄에 하나씩 입력된다. (0 <= wi, vi <= 100)
둘째 줄부터 n+1째줄 까지 물건들의 정보가 wi, vi가 한 줄에 하나씩 입력된다. (0 <= wi, vi <= 100)
출력 설명
배낭의 무게 W를 초과하지 않으면서 물건의 가격의 총합의 최댓값을 출력한다.
입력 예시 Copy
4 5
2 3
1 2
3 3
2 2
출력 예시 Copy
7