Knapsack Problem 이라고 불리는 DP의 대표적인 문제이다. 무게제한이 정해진 가방에 물건들을 담되 가치가 가장 높아지도록 담아야 한다. 물건마다 무게와 가치가 다르다.
이 문제도 여타 DP 문제처럼 점화식을 알아내면 쉽게 풀 수 있다. 다만 점화식을 알아내는게 매우 어렵다.
평범한 배낭 문제에 제시된 예제의 답을 구하는 DP테이블이다. 물건은 열(y)값으로 선택되고 무게는 행(x)값으로 선택된다.
즉 6,13 4, 8 3,6 이것들이 물건이며 (무게, 가치) 형태이다.
또한 첫 번째 값부터 점화식을 적용하기 위해, 0행과 0열은 모두 0으로 채워둬야 한다.
점화식은 이렇게 된다.
if x-yk >= 0:
dp[x][y] = max(dp[x][y-1], dp[x-yk][y-1] + val)
else:
dp[x][y] = dp[x][y-1]
yk는 현재 선택된 물건의 무게를 의미한다.
즉 dp[x][y] 값은 dp[x][y-1] 로써 좌측 값이지만,
x - yk >= 0: 일 경우 ( 현재 선택된 무게 - 현재 선택된 물건의 무게 값이 0 이상 -> 해당 값이 dp테이블에 존재하며, 물건을 담을 수 있다는 뜻 )
dp[x-yk][y-1] + val 값과 dp[x][y-1] 값(좌측 값) 중에 더 큰 값을 선택한다.
dp[x-yk][y-1] + val은 [현재 선택된 무게 - 현재 선택된 물건의 무게][y-1] 를 의미한다.
처음 보면 엄청 헷갈릴 수 있는데, 표를 천천히 따라가며 점화식을 적용해보면 이해될 것이다.
물론 점화식을 스스로 알아내야 문제를 푼 것이겠지만.. 나처럼 DP를 이제 입문한 사람은 정 모르겠으면 답을 보고 이해한 후, 문제를 해결하는 능력과 시야를 키우는 것도 좋다고 생각한다.
'Algorithm > Dynamic Programming' 카테고리의 다른 글
[Baekjoon 11053 / Python / 실버2] 가장 긴 증가하는 부분 수열 (0) | 2024.08.22 |
---|---|
[Baekjoon 15486 / python / 골드5] 퇴사2 (0) | 2024.04.24 |
[Baekjoon 9251 / python / 골드5] LCS (0) | 2024.04.07 |
[Baekjoon 9084 / python / 골드5] 동전 (0) | 2024.04.06 |
[Baekjoon 1904 / python / 실버3] 01타일 (0) | 2024.04.05 |