import sys
def solution(n, k, stuffs):
dp = [[0] * (k+1) for _ in range(n+1)]
stuff = [(0, 0)]
stuff.extend(stuffs)
for i in range(1, n+1):
weight, val = stuff[i]
for j in range(1, k+1):
if weight > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)
return dp[n][k]
n, k = map(int, sys.stdin.readline().split())
stuffs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
print(solution(n, k, stuffs))
유명한 문제인 0-1 Knapsack Problem이다.
DP배열을 정의하는데 어려움을 겪어서 풀이에 실패하여 다른 여러 풀이를 참고하였다.
먼저 2차원 DP배열은 다음과 같이 정의할 수 있다.
dp[i][j] : i번까지의 물건만 존재하고 무게가 j일 때의 최대 가치.
그리고 해당 dp 배열을 채워가면 답을 찾을 때는 다음과 같은 원칙을 따른다.
dp[i][j] = dp[i-1][j]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)