💼 배낭 문제는 쉽다!

라고 생각했었다. 워낙 유명한 문제이기도 하고 dp 문제 기본 예제 단골 손님이다...

하지만 직접 풀어보려니 어떻게 점화식을 짜야 할 지 쉽게 떠오르지 않았다.
누구나 맞기전에는 계획을 가지고 있다... ㅠ 디피는 항상 어려운 듯 하다..

🤔 나는 왜 떠올리지 못했을까?

가장 나에게 헷갈렸던 부분은 한번 담은 물건은 두 번 담을 수 없다는 것이었다.
분명 무게 k에서 1씩 증가시키면서 최대 가격을 확인하는 것이고, 그렇게 식을 구성하려 했다.

하지만 단순히 무게 k를 본다면 전에 어떤 물건을 담았는지 알 수 없었다. 여기서 막히고 말았다.
분명 2중 포문을 작성하면 될텐데,, 라고 생각했지만 어떻게 메모이제이션하지..? 라는 생각에 꼬여버렸다.

여러 블로그를 참고해서 점화식도 보고 어떻게 접근했는지 공부해 보았다.

✍️ 표를 그려보자?

말은 쉽다. 근데 막상 코딩테스트가 되면 잘 떠오르지 않는다. 미리 많은 연습을 하고 들어가자.

사실 LCS 문제랑 결이 같다는 생각이 많이 들었다. 같은 dp이기도 하고, 핵심은 fractional 하지 않고 한 번만 사용되는 물건들을 기준, 무게 기준으로 2차원 배열의 표를 그려나가면 되는 형식이다.

그렇게 생각하니 아이템의 개수를 나타내는 i, 무게 k의 dp[i][k] 라는 배열을 만들고 점화식을 구성하였다.

w >= weight[i] ? max(dp[i-1][w], dp[i-1][w-weight[i]] + v[i]) : dp[i-1][w]

와! 이해하니 외우지 않아도 기억해 낼 수 있다!

그렇다면 스스로에게 질문을 해보고 싶다.

dp[i-1][w]은 무엇을 의미할까?

이 부분이 LCS문제 와 비슷하다고 생각이 된다. LCS는 i-1이 의미하는 것은 지금 i의 길이 문장보다 하나가 적을 때의 최대 값을 나타낸다.

배낭 dp 문제도 마찬가지이다. 지금 물건을 고려하지 않은 상태(전에 물건만 가지고 있는 상태)에서 w 만큼의 무게를 담을 수 있는 최댓값을 나타낸다.

w >= weight[i]는 무엇을 의미할까?

w >= weight[i] 를 만족한다는 것은 지금 기준의 물건을 담을 수 있어? 라는 것을 물어보는 것과 같다. 그래서 3번째 물건이던 첫번째 물건이던 일단 최소로 자기만이라도 들어갈 자리를 만족하는 지에 대한 질문이라 생각한다.

만약 w>=weight[i]를 만족하지 않는다면 어차피 변동도 (물건이 더 생겨도 가방에 자리가 없는 상황) 없고 여전히 전에 물건들만 사용해도 가장 큰 상태가 되기 때문에 바로 dp[i-1][w] 를 넣어준다.

실전 문제

역시 사람은 직접 겪어 봐야 안다.

https://www.acmicpc.net/problem/12865

평범한 배낭 문제를 위에 점화식으로 풀어보자!

내가 쓴 정답은 링크로 남겨 놓겠다.

https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_12865.py