https://www.acmicpc.net/problem/12865
제발,, 가방,, 들고가지 말아주라,,,
택배로 짐 부쳐주라..,.
hoxy 냅색 알고리즘을 모르신다면,, 함 읽어보세요~! (🔗 링크)
냅색 알고리즘은 유명한 dp 문제 중 하나이다.
한마디로 가방에 물건을 최대치로 담고, 최대의 가치를 구하면 된다.
이때 ⭐️ 특정 물건을 담지 않을 때, 최선의 값이 나올 수 있다는 점을 고려해야 한다.
가방에 k
kg 까지 담을 수 있고, 아이템의 개수는 n
개 이다.
우선 dp 배열을 만들어줬다.
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
# dp[i][j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치
# ( i = 1 ~ n / j = 1 ~ k )
# 현재 물건의 무게 w, 현재 물건의 가치 v
w = bag[i][0]
v = bag[i][1]
현재 물건의 무게가 w
, 현재 물건의 가치가 v
일 때,
j
보다 w
가 큰 경우에는 가방에 물건을 담을 수 없다.
그럴 땐 dp[i][j]
에 이전 값 dp[i-1][j]
를 그대로 담아준다.
만약 j가 w보다 같거나 클 땐, 물건을 담을 수 있다.
하지만 현재 물건을 담지 않았을 때와 담았을 때 가치를 비교해준 뒤 더 큰 값을 넣어줘야 한다.
[현재 물건을 담았을 때 가치]
dp[i][j] = dp[i-1][j-w] + v
# dp[i-1][j-w] : 현재 물건을 담기 직전, 갖고 있던 최대 가치
# v : 현재 물건의 가치
[현재 물건을 담지 않았을 때 가치]
dp[i][j] = dp[i-1][j]
import sys
input = sys.stdin.readline
n,k = map(int,input().rstrip().rsplit())
bag = ['dummy']
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for _ in range(n):
row = tuple(map(int,input().rstrip().rsplit()))
bag.append(row)
for i in range(1,n+1):
for j in range(1, k+1):
# 현재 물건의 무게 w, 현재 물건의 가치 v
w = bag[i][0]
v = bag[i][1]
# 물건을 담을 수 있을 때
if j >= w:
# (현재 물건을 담지 않았을 때 갖는 최댓값 vs 현재 물건을 담았을 때 갖는 최댓값)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
else:
dp[i][j] = dp[i-1][j]
print(dp[n][k])