Knapsack 문제

어떤 아이템을 나타내는 배열(하위 배열에는 두 개의 정수를 가진 배열)이 제공됩니다. 첫번째 정수는 아이템의 값이며 두번째 정수는 아이템의 무게입니다. 그리고 배낭의 최대 용량을 나타내는 정수 capacity를 입력 받습니다.

우리의 목표는 아이템들의 무게의 합계가 배낭의 최대용량을 넘지 않게 배낭에 집어넣는 것과 동시에 아이템들의 값의 합계를 최대화하는 것 입니다.

선택한 아이템들의 최대값을 만들수 있는 아이템의 배열을 반환하는 함수를 작성하세요.

배낭의 최대값을 만드는 아이템들의 조합이 여러 개일 경우 함수는 그 중 한 항목을 반환하면 됩니다.

예제 1

입력

items = [[1, 2], [4, 3], [5, 6], [6, 7]]
capacity = 10

출력

[[4, 3], [6, 7]]