문제 이름은 평범한 배낭이지만 전혀 평범하지 않다고 느꼈다. 한참을 고민하다가 검색을 했지만 너무 어려웠다. 대표적인 DP 문제라고 하는데 knapsack 알고리즘을 이용해서 풀어야 한다. 입력값을 w 배열과 v 배열에 삽입하고 각 무게와 가치를 계산해서 dp배열에 가치의 최댓값을 넣어주면 된다. 가장 이해하기 어려웠던 부분은 아래의 코드인데 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); 이전에 계산했던 가치, 남은 무게의 가치 + 현재 가치 중 큰 값을 저장하는 부분이다. j - w[i] 는 j의 무게에서 현재 아이템의 무게를 뺀 값이다. 이 값은 dp[i-1][j - w[i]] 에 이미 저장되어 있고 이 값에 현재 아이템의 가치를 더한..