📌 냅색 알고리즘

배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다.

주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다.

🔧 풀이 과정

내 배낭의 용량(K) = 7
물건의 개수(N) = 4

---

start!

첫번째 물건 무게 = 6
현재 내 배낭 무게 = 0

6+0 < 7 (배낭 용량) --> 통과

---

현재 내 배낭 무게 = 6
두번째 물건 무게 = 4

4+6 > 7 (배낭 용량) --> 불가

---

choice

1. 첫번재를 버린다.
2. 두번째를 담지 않는다.

   당장은 첫번째 가치가 13이므로 첫 번째가 맞다. 하지만 후에는 어떤 것을 담아야 더 가치 있을지 모른다.

---

알고리즘 투입

• 물건 개수(n) x 배낭 용량(k)의 2차원 배열 d[n][k] 생성.

• 물건을 선택할 때마다 최대 가치를 판별하도록 한다.

• d[n][k]는 n번째 물건 까지 확인했을 때, 무게가 k인 배낭의 최대 가치이다.

• 현재 담을 물건의 인덱스 = i
• 현재 가방 허용 용량이 = j
• 현재 담을 물건의 무게 = weight
• 가치 = value

물건을 배낭에 담을 때

1. 현재 배낭의 허용 무게 < 넣을 물건

j < weight
d[i][j] = d[i-1][j]

2. 현재 배낭의 허용 무게 > 넣을 물건

2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.

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

구현 코드

# 배낭문제
n, k = map(int, input().split())

stuff = [[0,0]]
for i in range(n):
    w, v = map(int, input().split())
    stuff.append([w, v])

bag = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, k + 1):
        w = stuff[i][0]
        v = stuff[i][1]

        if j < w:
            # weight보다 작으면 위의 값을 그대로 가져온다
            bag[i][j] = bag[i - 1][j]
        else:
            #  max(현재 물건 가치 + knapsack[이전 물건][현재 가방 무게 - 현재 물건 무게], knapsack[이전 물건][현재 가방 무게])
            bag[i][j] = max(v + bag[i - 1][j - w], bag[i - 1][j])

print(bag[n][k])