[백준 12865] 냅색 알고리즘(DP) - 파이썬 Python

평범한 배낭 

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력

4 7
6 13
4 8
3 6
5 12

예제 출력

14

---

냅색(Knapsack) 알고리즘

냅색 알고리즘은 유명한 DP 문제 중 하나입니다.

가방에 담을 수 있는 무게엔 한계가 있고, 각 물건엔 가치가 정해져있습니다.
가방에 최대치로 물건을 담았을 때, 최대의 가치값을 구하는 문제입니다.

 냅색 알고리즘은 두가지로 나뉩니다.

 

1. Fraction Knapsack :  물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다.
   남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣으면 됩니다.
2. 0-1 Knapsack :  물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다.
   = 이 문제에 해당하는 유형으로 dp로 해결할 수 있습니다.

---

알고리즘

물건의 종류를 n, 가방의 최대용량을 k라고 할 때,

x축엔 가방 1~k의 무게, y축에는 물건의 갯수 n만큼의 배열을 만들어줍니다.

 

행을 차례대로 돌면서 알고리즘을 수행해 줍니다.

 

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

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

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

1	2	3	4	5	6	7
0	0	0	0	0	13	13
0	0	0	8	8	13	13
0	0	6	8	8	13	14
0	0	6	8	12	13	14

---

파이썬 코드

#Knapsack
import sys
input = sys.stdin.readline
n, k = map(int, input().split())

stuff = [[0,0]]
DP = [[0] * (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):
        w,v = stuff[i]
        if j >= w:
            DP[i][j] = max(DP[i-1][j] , DP[i-1][j-w] + v)
        else:
            DP[i][j] = DP[i-1][j]

print(DP[i][k])