말하는 컴공감자의 텃밭

배낭 문제이다. 초등학교때 이런유형 문제 수학시간에 나왔던거 같아 하나하나 다 따지자니 중복이 많으므로 범위를 나눠서 큰 문제를 푸는 DP를 선택했다. 배낭의 무게에 여유가 있다면 해당 물건을 담고, 이후 가방에 더이상 넣을 수 없다면 배낭 안의 물건과 가치를 비교해서 넣어주면 되겠다. 2차원 배열로 가방의 순서대로 진행하되, 무게를 저장해줬다. DP[ i ][ j ] 를 설명하면 i번째 물선 순서에 j의 무게를 담을 수 있는 가방 상황에서의 가치를 담고있다. 표로 정리해보면 무게 최대는 9Kg라 가정. W는 무게, V는 가치이다. 세로는 가방 무게인 J를 나타내고, 가로는 물건의 순서를 뜻한다. 초기에는 아무것도 들어있지 않으므로 0이다. DP[1][6] 이후로는 무게 6의 가치8 물건을 넣을 수 있으..