풀이 아이디어

x축 배낭에 넣은 무게
y축 아이템 무게

y축에 무게 3,4,5,6인 물건이 있을 때
y=1이면 무게 3인 물건만 있을 때 최대 가치
y=2이면 무게 3,4인 물건만 있을 때 최대 가치
y=3이면 무게 3,4,5인 물건만 있을 때 최대 가치
y=4이면 무게 3,4,5,6인 물건만 있을 때 최대 가치

값을 갱신하는 방식

if x-weight < 0:
            graph[y][x] = graph[y-1][x]
        else:
            graph[y][x] = max(graph[y-1][x], graph[y-1][x-weight] + value)

의사 코드

풀이 코드

import sys
input = sys.stdin.readline
# 입력 받기 
n,k = map(int,input().rstrip().split())
# 가로: 배낭 무게, 세로: 아이템 무게
graph = [[0]*(k+1) for _ in range(n+1)]
items = [(0,0)]

for _ in range(n):
    weight,value = map(int,input().rstrip().split())
    items.append((weight,value))

# 아이템을 하나씩 넣어보며 최대 가치를 구한다.
for y in range(1,n+1):
    weight,value = items[y]
    for x in range(1,k+1):
        if x-weight < 0:
            graph[y][x] = graph[y-1][x]
        else:
            graph[y][x] = max(graph[y-1][x], graph[y-1][x-weight] + value)
print(graph[n][k])