[APS] 19. DP와 평범한 배낭 문제(0/1 Knapsack, Python으로 구현하기)

1. DP (Dynamic Programming)?

---

• 큰 문제를 작은 문제로 ‘쪼개어’ 생각하는 것

• 크게 위에서부터 아래로 문제를 쪼개서 내려가는 Top-down 방식과, 아래에서부터 더해 올라가는 Bottom-up방식이 있다.

• DP의 전형적인 유형이 몇 가지 있고, 평범한 배낭문제도 그 중 하나에 속한다.

2. 평범한 배낭문제

---

• 생각하기가 힘들어서 검색의 힘을 빌렸다. 그런데 검색을 안했으면, 내 머리로는 절대 생각해 내지 못했을 것 같다.

• DP에서 알고리즘의 벽을 느끼고 있다.

• 완전히 이해하고 작성하는 글이다.

• 문제는 백준 12865 평범한 배낭 글의 예제를 사용하도록 하겠다.

3. 준비과정

---

• 이차원 배열이 필요하다. 이차원 배열에는 각 상황에 대한 가치의 최대값을 저장한다.

• 예를 들어 배낭에 들어갈 수 있는 총 무게가 7이고, 들어갈 수 있는 보석의 무게와 가치는 다음과 같다고 하자.

• 가장 가치가 크도록 담는 방법의 수를 구하려고 한다.

# 각각 무게 / 가치 순이다.
6 13
4 8
3 6
5 12

# values = [13, 8, 6, 2]
# weight = [6, 4, 3, 5]

• DP의 핵심은 한번에! 답을 구해내는 것이다.

• 문제를 작게 쪼개기 위해서 한번에 배낭에 담는 것이 아닌, 작은 주머니라고 가정해서 풀이하는 과정이다.

1. 주머니의 무게가 0이면 ⇒ 어떤 보석도 넣을 수 없다. (보석은 편의상 1번부터 있다고 가정한다.) 보석번호가 0이면 ⇒ 보석은 없는 것이기 때문에 어떤 보석도 넣을 수 없다.

보석번호/주머니의 무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0

2. 보석의 무게가 > 주머니의 무게라면? ⇒ 담을 수 없기 때문에, 이 보석을 넣지 못했을 때 주머니의 최대 가치와 같다.
   1. 식으로 표현하자면 Bags[i][j] = Bags[i-1][j] ⇒ 예를 들어 1번 보석번호는 무게가 6이기 때문에 주머니의 무게가 5일때까지는 0이다. ⇒ 주머니의 무게가 6부터는 가치가 13이다.

   보석번호/주머니의 무게	0	1	2	3	4	5	6	7
   0	0	0	0	0	0	0	0	0
   1	0	0	0	0	0	0	13	13
   2	0
   3	0
   4	0

3. 보석의 무게가 ≤ 주머니의 무게라면? ⇒ 이 때 이 문제의 핵심인 점화식을 사용할 수 있다.
   1. i번째 보석을 포함하는 경우
      1. i번째 보석의 가치 + {i를 포함하지 않고, 무게는 (주머니의 무게 - i번째 보석의 무게)인 주머니의 값}
   2. i번째 보석을 포함하지 않는 경우
      1. i를 포함하지 않고, 주머니의 무게는 그대로인 것 충에 최대의 가치를 값는 값

   ⇒ 즉 max(a,b)를 사용해서 점화식을 만들 수 있다.

   보석번호/주머니의 무게	0	1	2	3	4	5	6	7
   0	0	0	0	0	0	0	0	0
   1	0	0	0	0	0	0	13	13
   2	0	0	0	0	8	8	13	13
   3	0	0	0	6	8	8	13	14
   4	0	0	0	6	8	12	13	14

---

4. 최종코드

---

import sys

N, K = map(int, sys.stdin.readline().split())
# 제 머리로는 절대 생각해 낼 수 없어 검색을 조금 했습니다.
# 최대한 검색을 지양하고 있지만 정말 머리가 뽀개질 것 같아서 검색을 했으니.. 양해 부탁드립니다. (ㅜ)


# 무게와 값어치를 나타내는 배열을 만들어 각각에 입력을 받았습니다.
weight = []
value = []
for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    weight.append(w)
    value.append(v)

# 배낭 함수
def knapsack(W, N, weight, value):
    # W : 총 가방에 담을 수 있는 무게
    # N : 짐의 개수
    # weight : 무게가 담긴 리스트
    # value: 가치가 담긴 리스트
    Bags = [[0]*(W+1) for _ in range(N+1)]

    # 이차원 배열인 Bags를 돌면서, 값을 갱신한다.
    for i in range(N+1): # 행
        for j in range(W+1): #열

            if i == 0 or j == 0: # 첫번째 행과 첫번째 열은 모두 0으로 초기화 시킨다.
                Bags[i][j] = 0

            elif weight[i-1] > j: # 만약 현재 보석의 무게가 가방무게를 초과했다면 => 이전 칸과 같이 작성한다.
                Bags[i][j] = Bags[i-1][j]

            else: # 점화식을 사용한다.
                # i번째 보석을 고른 경우 // i번째 보석을 고르지 않은 경우 중 더 큰값으로 갱신한다.
                Bags[i][j] = max(value[i-1] + Bags[i-1][j-weight[i-1]], Bags[i-1][j])

    return Bags[N][W]

print(knapsack(K, N, weight, value))

Uploaded by N2T