문제 61번: 배낭 문제 1

배낭의 부피를 나타내는 자연수 volume과 각 물건의 부피와 가치의 쌍이 담긴 배열 items가 주어질 때, 배낭에 담을 수 있는 물건들의 조합 중에서 가치의 합이 최대가 되는 경우를 반환하는 solution 함수를 작성하시오.

배낭에 아무 물건이 들어있지 않은 경우, 가치의 합의 최대는 0입니다.

참고 내용

배낭 문제(Knapsack Problem)는 담을 수 있는 부피가 정해진 배낭과, 고유한 부피와 가치를 가지는 여러 개의 물건이 주어졌을 때, 배낭에 담은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제입니다.

배낭의 부피 volume은 100,000 이하의 자연수입니다.
물건 정보 items는 물건의 부피 x와 물건의 가치 y의 쌍인 [x,y]을 원소로 가지는 이차원 배열입니다.
- items의 길이는 1 이상 20 이하입니다.
- x와 y는 각각 10,000 이하의 자연수입니다.

테스트케이스 번호	volume	items	return
1	23	[[4,1],[9,3],[10,10],[9,8],[5,9]]	20
2	20	[[4,9],[3,3]]	12
3	3	[[4,6],[10,10]]	0

1번 테스트케이스 설명

2번 테스트케이스 설명

부피가 20인 배낭에는 모든 물건을 담을 수 있습니다. 이 경우 가치의 합이 최대가 됩니다.
- 총 부피 : 4 + 3 = 7
- 총 가치 : 9 + 3 = 12

3번 테스트케이스 설명