👻 다이나믹 프로그래밍 - 냅색 알고리즘

⚽ 냅색(knapsack) 알고리즘

냅색 알고리즘은 유명한 dp 문제 중 하나이다.
냅색 알고리즘은 두 가지로 나뉜다.
(짐 싸기 문제는 dp로 풀 수 있는 경우가 많다 !!)

• 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제

Fraction Knapsack
Fraction Knapsack 문제는 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다.
남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣으면 된다.
= greedy로 해결 가능!

0-1 Knapsack
0-1 Knapsack 문제는 물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다.
= dp로 해결 가능!

0-1 knapsack

가방에 담을 수 있는 무게엔 한계가 있고, 각 물건엔 가치가 정해져있다.

• 가방에 최대치로 물건을 담았을 때, 최대의 가치값을 구하는 문제이다.

😀 언뜻보면 그리디 알고리즘과 비슷해(최적의 해를 구하기) 보이지만, 최적의 해가 나오지 않을 때도 있다.

예시 ) 가방에 15kg까지 담을 수 있고, 세가지 물건이 있다. 이때 가치를 최대로 가지려면 어떤 물건을 담아야할까?
[물건 A] 가치: 10, 무게: 13kg
[물건 B] 가치: 6, 무게: 6kg
[물건 C] 가치: 5, 무게: 6kg


그리디 알고리즘
가치를 최대로 갖도록 그때그때 최선의 선택을 하기때문에 물건 A를 담고 끝이 난다.


정답
물건 A를 담지 않고, B와 C를 담는다.

오히려 특정 물건을 담지 않았을 때가 최선의 선택일 수 있음을 고려해주는 것이 냅색 알고리즘의 핵심인 것 같다.

알고리즘

⚽ 냅색 알고리즘은 다이나믹 프로그래밍 (DP)를 이용하면 문제를 해결할 수 있다.

x축에는 가방 1~k개의 무게, y축에는 물건의 갯수 n만큼의 배열을 만들어준다.
행을 차례대로 돌면서 알고리즘을 수행해 줄 것인데,

• 현재 물건(i)이 해당 열의 무게보다 크면, 담을 수 없는 물건이므로 [이전물건][현재무게] (knapsack[i-1][j]) 그대로 적용해준다.

• 현재 물건이 해당 열의 무게보다 같거나 작으면 담을 수 있으므로, 넣어줬을 때를 계산한다. 현재 물건 + [이전물건][j-현재물건] (weight + knapsack[i-1][j-weight])

• 위에서 구한 무게와 [이전물건][현재무게]를 비교해서 그 중 더 큰 값을 채택한다.

• 결국 knapsack[n][k]는 k무게일 때 최댓값(최대 가치)을 가리킨다.

수식

결국 수식으로 표현하면 다음과 같다.

knapsack[i][j] = max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])

knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

• 결국 아래와 같이 만들어진다.

이 문제의 정답은 dp[N][K]에 들어있다.

• 그 이유는 1부터 N개의 모든 물건들을 살펴보고, 배낭 용량이 k였을 때 이 배낭에 들어가 있는 물건들의 가치합의 최댓값이 들어가게 될 것이기 떄문이다.

---

이제 dp[i][j]의 점화식을 나타낼 수 있다. 이 문제는 dp[i][j]의 값을 차례대로 채워나가야 한다.
dp[i][j]에는 dp[i-1][j]와 dp[i-1][j-w] + v의 값 중 더 큰 값이 들어가게 된다.

1) i가 현재 물건의 무게 w보다 작을 때

• 현재 물건을 담을 수 없으므로 이전의 값을 복사한다.
  dp[i][j] = dp[i][j-1]

2) i가 현재 물건의 무게 w와 같거나 클 때

• 현재 물건을 담을 수 있다.
• 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
• 현재 물건의 가치는 v 이다.
  dp[i][j] = max( dp[i][j-1] , dp[i-w][j-1] + v)

---

물건을 배낭에 담을 때,
1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다.
2. 현재 물건을 넣을 수 있다면, 다음 중 더 나은 가치를 선택한다.

• -1)현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.
• -2)현재 물건을 넣지 않고 이전 배낭 그대로 가지고 간다.

위 과정을 식으로 나타내면,
현재 담을 물건의 인덱스를 i, 현재 가방 허용 무게가 j, 현재 담을 물건의 무게 weight, 가치 value라고 하면

1. j < weight: dp[i][j] = dp[i-1][j]
2. dp[i][j] = max(dp[i-1][j-weight] + value, dp[i-1][j])

2-1 과정에서 현재 넣을 물건의 무게만큼 배낭에서 뺀다고 한 부분에 의문점이 들 수 있다.

• 현재 넣을 무게와 똑같은 무게의 물건이 없으면 어떻게 빼는가? 물건이기 때문에 쪼개지지 못하는데 ?

하지만 현재 넣을 물건의 무게만큼 뺀 배낭에는 그 무게의 배낭이 가지는 최대 가치가 저장되어 있다. 그래서 상관없다.

⚽ 물건의 최대 가치는 dp[가방 크기][물건의 개수]로 구할 수 있다 !

코드

import sys

N, K = map(int, input().split())
stuff = [[0,0]]
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for _ in range(N):
    stuff.append(list(map(int, input().split())))


#냅색 문제 풀이
for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = stuff[i][0] 
        value = stuff[i][1]
       
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] #weight보다 작으면 위의 값을 그대로 가져온다
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

print(knapsack[N][K])

👻 다이나믹 프로그래밍은 작은 단계부터 올라가기 때문에 보석이 한개만 있을 때부터 천천히 올라가기. 문제를 시각화할 수 있어야 한다 !!

---

최적화

해당 문제를 dp 1차원 배열로 해결할 수 있다. (최적화)
이제 dp[j]가 가지는 값의 의미를 알아보자

dp[j] : 가방에 j라는 무게(weight)까지(최대 무게) 담을 수 있을 때 이때 이 가방이 가질 수 있는 최대 가치(보석)를 의미한다. (j는 가방 무게의 한계)

이제 아주 작은 단위부터 생각해보자.

• 보석이 하나만 있다고 생각하고 접근

보석의 무게, 가치가 5,12일 때를 생각해보면 dp[j]에서 j는 5부터 값을 넣을 수 있다.

• 왜냐하면 j는 가방이 담을 수 있는 최대 무게라고 했잖아. j가 5보다 작으면 애초에 담을 수가 없다. 즉 가방의 무게가 j이상일 때부터 담을 수 있다. (물론 담는다는 가정.)

dp[j-w] + v 즉 현재 보석(5,12)를 담는다고 가정을 했기 때문에 -5를 해줘야 한다. + 현재 보석의 가치 12를 더해준다. (담는다고 가정을 했기 때문 !)

한칸 더 가서 dp[j ==6]에 대해서 생각해보자.
(5,12) 보석을 담을 수 있으므로 d[j-w] + 12를 적용가능!

👻 이제 가방의 최대 무게 j == 10이 될 때가 중요
dp[j-w] + v인데 dp[5] + 12로 해석된다. 근데 이미 dp[5]의 값은 구해놨기 때문에 기존 값보다 커서 갱신된다 ! 이런식으로 각 보석들을 하나씩 적용하면서 가방의 최대 무게일 때의 최대 가치를 저장해나가면 된다.

• 이제 보석 하나를 적용해 봤다. 다른 보석을 담을 때는 이제 비교를 하게 된다.
• (3,8) 보석을 또 적용한다고 생각해보자.

해당 보석은 j == 3 일 때부터 (가방이 담을 수 있는 최대 무게가 3일 때부터) 적용할 수 있다.
근데 이제 j == 5일때...
dp[5 - 3] + 8을 그대로 적용할 것인가 ? NO

• 이유는 해당 값은 8인데, 기존에 저장되어 있는 dp[5]는 12를 갖는다.
• 결국 기존에 값이 더 크다면 (비교를 해야한다는 뜻) 그걸 유지하면 돼

결국 기존 값보다 더 큰 가치를 가지는 값이 나와야 갱신이 되는거야 !

👍 코드의 변화

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

data = []
n, limit = map(int, input().split()) #보석 종류, 무게 한계값
for _ in range(n):
    a,b = map(int, input().split())
    data.append((a,b)) #무게, 가치
data.insert(0,(0,0)) #0번 인덱스 사용안함
dp = [[0] * (limit+1) for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(1,limit + 1):
        weight = data[i][0] # 현재 물건 무게
        value = data[i][1] # 현재 물건 가치

        if j < weight: #현재 물건 담을 수 없으니 이전꺼 가져와야함
            dp[i][j] = dp[i-1][j]
        else: #현재 물건 담을 수 있음
            dp[i][j] = max(dp[i-1][j-weight] + value, dp[i-1][j])

print(dp[n][limit])

• 2차원 DP 테이블 사용

👻 냅색 알고리즘 최적화

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

data = []
n, limit = map(int, input().split()) #보석 종류, 무게 한계값
dp = [0] * (limit + 1)

for i in range(n):
    w,v = map(int, input().split()) #무게, 가치
    for j in range(w , limit + 1): #현재 적용하고자 하는 무게부터 돌아야지
        #이렇게 안할거면 if문으로 따로 조건 걸어야해!
        dp[j] = max(dp[j], dp[j-w] + v)  #현재 보석을 가방에 담을 것이라고 가정한 값이 dp[j-w] + v 이다.

print(dp[limit])

• 1차원 DP 테이블 사용

dp 테이블을 2차원에서 1차원으로 줄여서 사용할 수 있다 !

dp vs 완탐(DFS, BFS)

시간초과 안날 것 같으면 완탐도 생각하자.

참고 블로그

ref.냅색 알고리즘