https://www.acmicpc.net/problem/12865
시간 2초, 메모리 128MB
input :
- N K(1 ≤ N ≤ 100)(1 ≤ K ≤ 100,000)
- W V(1 ≤ W ≤ 100,000)(0 ≤ V ≤ 1,000)
output :
- 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력
처음엔 그리디를 이용해서 할 수 있을 까 했지만, 모든 물건들을 넣을지 말지에 대한 판별이 필요하다.
그래서 해야 하는 것은?
우리는 (무게, 가치) 를 묶어서 입력을 받는다. 그리고 모든 경우에 이 물건을 가지고 가는 것이 가치가 더 커지는지에 대한 확인이 필요하다.
1번째로 입력 받은 물건을 확인하기 전. 0 번째일 때는 아무것도 없기 때문에
temp 를 0으로 초기화 해준다.
temp에는 current_idx 이전인 prev_idx 까지의 각 무게에서 최대의 가치를 담고 있는 것이다.
current_idx의 무게, 가치를 wei, val 이라 할 때.
현재의 wei 를 담으려면 담으려는 배낭의 무게(w) 가 더 커야 한다.
1. 현재의 wei > w:
이 경우에는 담을 수가 없다. 그렇다면 이전에 이 물건을 넣기 전까지의 최댓값 temp[w] 값을 ans[w]에 넣어준다.
2. else:
인제 무게가 충분해 져서 넣을 수 있게 되었다면 2가지 경우를 비교해야 한다.
- val + temp[w - wei] : 현재의 물건을 담았을 때의 가치 + 남는 무게를 채울 때 얻을 수 있는 가치
- temp[w] : 이전의 물건 까지를 담았을 때 최대의 경우.
이 두가지를 비교해 더 큰 값을 넣어준다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = []
for i in range(n):
w, v = map(int, sys.stdin.readline().split())
data.append((w, v))
# 바로 이전 값을 저장해놓는 DP 용
temp = [0] * (k + 1)
ans = [0] * (k + 1)
for wei, val in data:
# 기준이 되는 w (배낭 무게) 임.
for w in range(k + 1):
if wei > w:
ans[w] = temp[w]
else:
ans[w] = max(val + temp[w - wei], temp[w])
for idx, item in enumerate(ans):
temp[idx] = item
print(ans[-1])
