🔥

문제

헬로바자회에서 N개의 물건을 나눠주는데, 각 물건은 무게 wi와 가치 vi가 정해져있다.


욕심이 많은 윌리는 물건을 다 가져가고 싶지만, 가방이 낡아 W보다 무거운 무게를 담으면 가방이 끊어지고 만다.


윌리가 가방이 끊어지지 않는 선에서 가져갈 수 있는 물건 가치의 합의 최대를 구하자.

입력

첫째 줄에 물건의 개수 N(1 ≤N ≤ 100)과 가방의 한계 W(1 ≤ W ≤ 10^5)가 주어진다.


둘째 줄부터 N개의 줄에 물건의 무게 xi(1 ≤ xi ≤ W)와 물건의 가치 vi(1 ≤ vi ≤ 10^9)가 주어진다.

출력

첫째 줄에 윌리가 얻을 수 있는 물건 가치의 합의 최대값을 출력한다.

예제 1 입력

2 1
1 1
1 1

예제 1 출력

1

예제 2 입력

3 8
3 30
4 50
5 60

예제 2 출력

90

Source

n, w = map(int, input().split())
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
	x, v = map(int, input().split())

	for j in range(1, w + 1):
		dp[i][j] = dp[i - 1][j]
    # 현재 물건을 가방에 담을 수 있는 경우 (즉, 현재 무게 j가 물건의 무게 x보다 크거나 같을 때)
		if(j - x >= 0):
      # 물건을 담지 않는 경우(dp[i-1][j])와 현재 물건을 담는 경우(dp[i-1][j-x] + v)를 비교하여 더 큰 값을 저장
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - x] + v)

print(dp[n][w])

참고