https://www.acmicpc.net/problem/12865
냅색 알고리즘 문제의 정석
n개의 물건,,k 무게까지 버티는 가방,, 최대 가치,,
0. 입력 받기
for _ in range(n):
row = tuple(map(int,input().rstrip().rsplit()))
bag.append(row)
1. dp 배열 정의하기
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
dp[i][j]
= 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치
2. 현재 물건을 담았을 때 vs 담지 않았을 때 비교하기
# 현재 물건의 무게 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]
import sys
input = sys.stdin.readline
n,k = map(int,input().rstrip().rsplit())
bag = ['dummy']
# dp[i][j] = 물건 무게의 합이 j일때, 처음 i개의 아이템 중 담을 수 있는 최대 가치
# ( j = 1 ~ k )
# j가 현재 물건의 무게 w보다 작을때 : w를 담을 수 없으므로 전의 값을 복사한다.
# dp[i][j] = dp[i-1][j]
# j가 현재 물건의 무게 w와 같거나 클 때 : 물건을 담았을 때와 담지 않았을 때 max 값을 찾아준다.
# dp[i][j] = max( dp[i-1][j] , dp[i-1][j-w] + v)
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])