배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다.
배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데,
d[j] :가방의 무게가 j일 때, 최대 가치의 값
d[j] = max( d[j-w]+v , d[j] )
가방에 w의 무게의 물건이 담겼을 때와, 안담겼을 때를 비교하여 최대 가치의 값을 담아줌.
# n : 물건의 수 / k : 무게 제한
n, k = map(int, input().split())
d = [0]*(k+1)
for _ in range(n):
w,v = map(int,input().split())
for j in range(w,k+1):
d[j] = max(d[j], d[j-w]+v)
print(d[k])
# n : 물건의 수 / k : 무게 제한
n, k = map(int, input().split())
d = [0]*(k+1) #인덱스번호 k까지
for _ in range(n):
w,v = map(int,input().split())
for j in range(k,w-1,-1):
d[j] = max(d[j], d[j-w]+v)
print(d[k])