[SW 정글 26일차] Knapsack Problem 이해하기

오늘 푼 문제 중에서 Dynamic Programming을 사용하여 푸는 Knapsack Problem을 만났다.

오늘 공부시간을 DP문제풀이에 쏟은 만큼 Knapsack Problem의 문제 접근법에 대해 정리해보려고 한다.

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

12865번: 평범한 배낭

 

 

 

1. 문제가 뭔데?

출처: https://en.wikipedia.org/wiki/Knapsack_problem

최대 용량이 정해진 배낭에 무게와 값어치가 다른 물건들을 담으려고 하는데 담긴 물건들의 값어치의 총합이 최대인 경우를 찾는 것이다.

위의 사진을 보면 4kg(10달러), 1kg(2달러), 2kg(2달러), 1kg(1달러) 4개의 물건을 담아서 총 15달러가 최대 값어치가 된다.

문제에 주어지는 물건들의 개수가 완전탐색을 할 수 있을 만큼 적다면 좋겠지만 그리 쉽게 풀 수 있는 문제가 아니다.

 

 

 

2. 문제 접근 방법

위 그림에서 1kg-1달러 물건을 제외하고 4개의 물건과 15kg 한도 배낭으로 생각해보자.

지금은 4개의 물건이여서 완전탐색으로 문제 풀이가 가능하지만 물건이 무수히 많을 경우를 생각해서 지금 주어진 문제를 하나의 큰 문제라고 생각하고 부분문제(sub problem)으로 쪼개서 접근하는 것을 생각해보자.

 

각 물건들은 배낭에 들어가는 경우와 들어가지 않는 경우로 나뉠 수 있다.

그러면 큰 문제가 아래의 그림과 같이 작은 문제로 나뉠 수 있다.

(A: 12Kg, 4달러/ B: 2kg, 2달러/ C: 1kg, 2달러/ D: 4kg, 10달러)

두 개의 부분 문제로 나뉘어졌고 이 부분 문제도 다시 부분 문제로 나뉠 수 있다.

끝까지 나눠보면 아래의 그림과 같다.

 

그림이 너무 복잡해졌는데 간단하게 말하면 각 상황에서 하나의 물건을 넣을지 말지를 결정해서 또 다른 부분 문제로 나뉘는 것이다.

결과적으로 14달러가 정답이 된다.

그러면 이 문제를 점화식으로 나타내면 어떻게 될까?

점화식을 보면 현재 배낭의 무게 한도보다 들어가고자 하는 물건의 무게가 크면 이전의 값어치를 그대로 가져간다.

그렇지 않고 물건이 들어갈 수 있는 경우에는 넣은 경우와 넣지 않은 경우 중에 큰 값을 결정한다.

 

 

 

3. 코드로 구현해보기

해당 문제를 코드로 구현해보면 어떻게 될까?

나는 위 문제를 top-down방식이 아닌 bottom-up방식으로 dp table을 채워가면서 최종 정답을 얻는 식으로 코드를 구현했다.

# dp 테이블 생성
# 열은 배낭의 남아있는 무게, n은 물건의 갯수
matrix = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

# things는 물건의 무게와 값어치를 담고 있는 배열
for i in range(1, n + 1):
    for j in range(1, k + 1):
        weight = things[i][0]
        value = things[i][1]
        #점화식 구현
        if things[i][0] <= j:
            matrix[i][j] = max(matrix[i - 1][j], matrix[i - 1][j - weight] + value)
        else:
            matrix[i][j] = matrix[i - 1][j]
    
print(matrix[n][k])

어제의 LCS에 이어 재밌는 문제를 마주한 것같다.

풀고 나면 재미있는데 다음 문제를 보면 또 좌절의 연속이 이어진다...

내 힘으로 풀 수 있는 DP문제가 나올 때까지 노력해보자.

---

[오늘의 나는 어땠을까?]

어제부터 다이나믹 프로그래밍(dp)문제를 풀고 있다.

정말 어렵다.... 답을 보지 않는 이상 어떻게 문제에 접근해야할지 감이 안온다.

분할 정복과 비슷한듯 더 어렵고 테이블을 쓴다는 것이 너무 어렵다.

그래도 계속해서 많은 문제들을 풀다보면 문제 접근법에 익숙해질 수 있다고 생각하며 계속 해보려고 한다.

 

내일부터는 아침에 일어나서 짧은 시간이라도 운동을 하려고 한다.

근력운동은 에너지 소비가 심할 것 같으니 런닝이라도 뛰면서 건강관리를 하려고 한다.

사실 들어오기 전부터 운동을 하려고 계획했는데 잠을 5시간정도 잘만큼 하루에 성장을 위한 주어지는 시간이 짧다고 느꼈고 어쩔 수 없이 운동을 포기했다.

운동없이도 건강히 잘 버텨왔는데 목요일부터 몸이 무기력하고 뻐근하고 더 이상 이러한 패턴으로 움직였다가는 건강때문에 공부를 못하겠다는 생각이 들었다.

그래서 주말 2틀만 아침 공부 1시간을 운동에 투자하려고 한다.

 

뭐든지 꾸준히 하고 싶다. 지금 계획한 운동이라는 것도.

 

---

<참고 자료>

https://www.youtube.com/watch?v=rhda6lR5kyQ&t=3s