가방 문제

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.

이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데, 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요?

또 한 각각의 종류별 보석의 개수는 무한히 많아서 여러 번 가방에 담을 수 있다. 입력 예제 4 11 5 12 3 8 6 14 4 8 출력 예제 28 풀이 방식 무게가 5이고 가치가 12인 첫 번째 보석들 기준으로 설명하겠습니다.

먼저 DP 테이블은 각각의 무게에 대응하는 최대 가치를 저장하는 테이블이다. 예를 들어 문제에서 제시하는 가방의 가용 용량이 5라면, DP 테이블은 0부터 5까지인 길이 6의 배열을 갖는다.

현재 보석을 토대로 DP 테이블을 채우면 사진처럼 현재 무게 대비 가치가 쭉 채워진다. 가방의 가용 무게가 5 ~ 9라면 가방이 가질 수 있는 각각의 최대 가치는...