[백준] 12865번: 평범한 배낭 (Knapsack Problem) - python

문제 보기

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

12865번: 평범한 배낭

 

 

 

 

---

풀이 및 코드

 

해당 문제는 knapsack problem로 배낭문제라고 풀리는 알고리즘 문제이다. 학교 다닐 때 배웠던 게 기억나는 데 knapsack만 기억나고 알고리즘은 기억이 나지 않아 오늘도 삽질을 좀 했다 ㅎ

 

 

처음에는 dp를 1차원으로 구성했고 해당 점화식을 바탕으로 풀었다.

 

dp[W] = max(dp[W], dp[W-w] + v)

 

dp는 W 무게의 가방을 채울 때 최대 가치를 저장했다. 따라서 아이템과 무게를 for문을 돌리면서 점화식을 계산해 dp를 채워가면서 문제를 풀려고 했다! 하지만 해당 아이템을 가방에 추가하는 dp[W-w] + v 코드가 작동할 때, 이전에 해당 아이템이 추가되었는 지 확인할 수가 없어 같은 아이테을 중복해서 넣는 문제가 발생했다.

 

나중에 알게 된 사실이지만 W를 역순으로 주어 reversed(range(1, k+1))로 준다면 해당 문제를 해결할 수 있다. 무게가 큰 것부터 채워지기 때문에 중복을 피할 수 있다. 이와 같이 코드를 작성한다면 다음과 같다. 

 

 

 

 

 

 

 

두번 째 방법은 dp를 2차원 배열로 구성하는 것이다. 

 

dp[i][W]에는 0~i 번째 아이템을 사용해 W 무게의 가방을 채울 때의 최대 가치를 저장한다.

만일 i번째 item의 w가 W보다 크다면(W < w) 해당 가방에 item을 넣을 수 없으므로 다음 점화식이 완성된다. 

dp[i][W] = dp[i-1][W]

반대의 조건에서는 아이템을 가방에 넣는 것과 넣지 않는 것을 비교해 더 큰 가치를 가지도록 해야한다. 아이템을 넣지 않는 경우인 dp[i-1][W]와 넣은 경우 dp[i-1][W-w] + v 를 비교해 주면 된다.

dp[i][W] = max(dp[i-1][W], dp[i-1][W-w] + v)

 

 

 

 

 

 

 

 

참고로 베이직하게 많이 쓰이는 방법은 2번째 방법이다. 하지만 첫 번째 방법도 같이 알아두는 것이 좋겠다!