0/1 배낭 채우기[파이썬 코드]

도둑이 배낭을 메고 보석가게에 침입했다. 🥷

각 보석들은 무게와 가격이 있고 도둑은 최대 용량이 W인 배낭🎒 에 가격 합이 최대가 되도록 보석을💎 담고자 한다.

배낭이 찢어지지 않는 선에서 가격의 합이 최대가 되도록 보석을 담는 방법은 어떻게 구할수 있을까?

가격 합이 최대가 되도록 보석을 배낭에 담지 않거나$($0), 담는$($1)경우를 각 보석마다 모두 고려해야 하기 때문에 “0/1 배낭 문제”라고 부르며 다이나믹 프로그래밍을 기반으로 동작한다.

배낭 채우기 문제 수행과정

• 배낭의 최대 용량 : cbw $($current bag weight)
• 보석의 무게 : w
• 보석의 가치 : v

i 번째 보석의 무게가 남은 배낭의 용량보다 크다면 해당 보석은 배낭에 넣을수 없고, 이전 배낭 그대로 가지고 가야한다.

cbw < w: dp[i][cbw] = dp[i - 1][cbw]

만약 i 번째 보석의 무게 남은 배낭의 용량보다 작다면 우리는 그 보석을 배낭에 넣을수 있다.

단, i 번째 보석을 배낭에 넣었을 때, 최적의 해$($배낭속 보석 가격의 합이 최대가 되는 해)가 보장되는지의 여부에 따라 보석을 넣을지 말지를 결정해야 한다.

• i번째 보석을 넣지 않는 경우

   보석을 넣지 않고 이전 배낭 그대로 가져 간다.
  

• i번째 보석을 넣는 경우

  보석의 무게 만큼 남은 배낭의 요량에서 뺀다. $($w - wci)

  넣은 보석의 가치를 최적의 해에 더해준다.

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

---

예를 들어서 배낭의 전체 용량이 5라고 가정하자. $($cbw = 5)

보석은 4개가 있고 각각의 무게와 가치는 다음과 같다고 하자. $($w, v)

$($2, 4), $($1, 1), $($4, 3), $($3, 2)

배낭의 최대 무게가 0일 때와 보석이 없는 경우엔 배낭에 넣을 수 있는 최대 가치가 0이기 때문에 첫 행과 첫 열을 0으로 초기화 해준다.

1. $($2, 4)

첫번째 보석 $($2, 4)를 배낭에 넣는 경우를 생각해 보자.

배낭의 최대 무게가 1일 때는, 첫번째 보석의 무게가 2이므로 배낭에 넣을 수 없다.

따라서 dp[1][1] = 0 이 된다.

배낭의 최대 무게가 2인 경우엔, 첫번째 보석의 무게가 2이므로 배낭에 넣을 수 있다.

따라서 dp[1][2]는 첫번째 보석의 가치 4가 된다.

그 이후의 무게도 1번째 보석의 무게보다 크기 때문에 배낭에 넣을 수 있으므로 전부 첫번째 보석의 가치 4로 초기화 해준다.

1. $($1, 1)

두번째 보석 $($1, 1)을 배낭에 넣는 경우를 생각해보자.

먼저 배낭의 최대 무게가 1인 경우, 두번째 보석의 무게가 1이기 때문에 배낭에 넣을 수 있다.

따라서 dp[2][1]은 두번째 보석의 가치 1이 된다.

이제 배낭의 최대 무게가 2인 경우를 생각해 보자.

두번째 보석의 무게가 1이기 때문에 배낭에 넣을 수 있다. 하지만 앞서 배낭에 넣었던 첫번째 보석의 무게가 2여서 두 보석을 같이 넣을 수 없다.

때문에 첫번째 보석을 빼고 두번째를 넣는 경우와, 두번째를 넣지 않고 예전 배낭 그대로 가져가는 경우중 더 큰값을 선택해야 한다. dp[i][cbw] = max$($dp[i - 1][cbw], dp[i - 1][cbw - w] + v)

dp[2 - 1][2] = dp[1][2] = 4이고,

dp[2 -1][2 - 1] + 1= dp[1][1] + 1 = 1 이므로

dp[2][2] = 4

나머지 배낭의 무게 3,4,5는 첫번째 보석과 두번째 보석의 가치를 더한 5가 들어간다.

1. $($4, 3)

세번째 보석은 무게가 4이기 때문에 배낭의 최대 무게가 4 이상인 케이스 부터 확인을 하면 된다.

1. $($3, 2)

4번째 보석 $($3, 2)는 배낭의 최대 무게가 4인 경우부터 보겠다.

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

dp[4 - 1][4] = dp[3][4] = 5

dp[4 -1][4 - 3] + 2 = dp[3][1] + 2 = 1 + 2 = 3

따라서 이전 배낭을 그대로 가져오는 편이 최적의 해를 보장한다. $($dp[4][4] = 5)

배낭의 최대 무게가 5인 경우,

dp[4 -1][5] = dp[3][5] = 5

dp[4 -1][5 - 3] + 2 = dp[3][2] + 2 = 4 + 2 = 6

모든 과정을 수행한 결과, 배낭의 최대 무게 5에 대한 최대 가치는 6이라는 것을 알 수 있다.

0/1 배낭 파이썬 코드

# 배낭의 최대 무게
beg_weight = 5

# 보석의 무게, 가치
dia_weight = [2, 1, 4, 3]
dia_value = [4, 1, 3, 2]
dia = [(0, 0)]

for i in range(len(dia_weight)):
    dia.append((dia_weight[i], dia_value[i]))

# 보석의 최대 가치 메모를 위한 dp
dp = [[0] * (beg_weight + 1) for _ in range(len(dia))]

print(len(dp))

for i in range(1, len(dia)):
    cdw = dia[i][0]    # i 번째 보석 무게
    cdv = dia[i][1]    # i 번째 보석 가치

    for cbw in range(1, beg_weight + 1):
        # 배낭의 최대 무게가 보석의 무게보다 작아서 담지 못하는 경우
        if cbw < cdw: dp[i][cbw] = dp[i - 1][cbw]
        # i 번째 보석을 넣는 경우와 그렇지 않는 경우의 최적 해를 비교
        else: dp[i][cbw] = max(dp[i - 1][cbw], dp[i - 1][cbw - cdw] + cdv)

# 배낭의 최대 무게에 대한 최대 가치 출력
print(dp[len(dia) - 1][beg_weight])