knapsack

dp

점화식 : knapsack[i][j]=max(knapsack[i−1][j],value+knapsack[i−1][j−weight])

각 셀 knapsack[i][j]는 i개의 아이템과 jkg 용량을 가진 냅색에서의 최대 가치를 나타냄

1. j-weight: 여기서 weight는 현재 고려하고 있는 아이템 i의 무게.
   j-weight는 현재 아이템을 냅색에 추가했을 때 남는 냅색의 용량을 의미함 -> 이 문제의 포인트

N, K = map(int, input().split())  # 갯수, 무게
stuff = [[0, 0]]  # 첫 번째 인덱스를 사용하지 않기 위해 [0,0]을 추가
knapsack = [[0 for _ in range(K+1)] for _ in range(N+1)]  # dp 테이블 초기화

for _ in range(N):
    stuff.append(list(map(int, input().split())))  # 무게, 가치

for i in range(1, N+1):
    for j in range(K+1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if j < weight:
            knapsack[i][j] = knapsack[i-1][j]  # 현재 무게를 담을 수 없다면 이전 아이템의 가치를 그대로 사용
        else:
            knapsack[i][j] = max(value + knapsack[i-1][j-weight], knapsack[i-1][j])  # 현재 아이템을 포함하거나 포함하지 않는 경우 중 최대값을 선택

print(knapsack[N][K])  # 최대 가치 출력