백준 12865: 평범한 배낭 (Knapsack문제 / with Swift )

Dynamic Programming문제의 일종으로 

매우 유명한 Knapsack 문제 (배낭문제) 이다. 

 

2차원배열의 열은 해당 1~ k(배낭의 최대 수용 무게) 까지 나타내게 되고, 

행은 가지고있는 물건의 수만큼 크기를 가진다.  (1 ~ n) n은 가지고있는 물건의 갯수

 

우리는 물건 n개를 차례로 순회하며,dp배열을 업데이트한다.

 

 dp[i][j]가 의미하는 것은, i 번째 물건까지 순회했을 때, j만큼의 무게를 채울 때의 가치의 최댓값이 된다. 

 

따라서 현재 순회중인 물건의 무게보다 적은 크기의 무게를 가리키는 열들에 대해서는, 업데이트가 필요 없으므로 이전 행의 값을 그대로 아래로 가지고 내려오면 된다.

 

현재 순회중인 물건의 무게보다 크거나 같은 무게를 가리키는 열에서는,

1.바로 위의 줄에 있는 값과,

2."현재 열의 무게 - 현재 물건의 무게"를 채울 수 있는 최고 가치 + 현재 물건의 가치 

이 두가지를 비교하여 더 큰 값으로 dp[i][j]를 채워주면 된다.