굉장히 유명한 문제이다.
Knapsack problem으로 알려져 있다.
[출처] https://www.geeksforgeeks.org/printing-items-01-knapsack/
문제에서 총 물품의 개수와 담을 수 있는 최대 무게가 입력으로 주어진다.
우리는 위의 표에서 볼 수 있는 것처럼 개수와 무게로 이차원 배열을 생성한다.
예를들어, dp[i][j] 이면 i개의 개수로 j의 무게를 채웠을 때, 최대 가치의 값이다.
따라서 매번 넣을 수 있는 개수마다 모든 물품을 확인하여 무게를 채운다.
코드로 확인해보자.
코드를 보면 i가 물건의 개수, j가 배낭의 무게이다.
만약 현재 고민의 대상인 물건의 무게가 현재 고민의 대상인 무게의 무게보다 무거우면 이전이랑 동일한 값으로 유지한다.
모든 물건을 대상으로 모든 무게에서 물건을 포함하는 지 안하는 지
두 가지의 선택을 비교한다.
점화식은 max(dp[i-1][j-w] + v, dp[i-1][j])
dp[i-1][j-w]는 물건을 넣는 것으로 선택했을 때, 현재 넣을 수 있는 개수에서 하나를 빼고 넣을 수 있는 무게에서 선택한 물건을 빼 이전에 구해놓은 결과를 현재 물건의 가치와 더한다.
예시로 설명하면 i=2, j=5일 때 우리가 넣기로 선택한 물건의 무게가 3이고 가치가 10이면 dp[1][2] (하나의 물건으로 무게를 2를 채운 경우) + 10이 물건을 넣었을 때의 가치이다.
Whiplash We Flash