백준 12865번 평범한 배낭
사용한 알고리즘: DP
pair을 사용해 각 물품의 <무게, 가치> 를 저장해주었습니다.
'dp[a] : a만큼 무게를 가방에 담을 때, 가장 큰 가치' 라고 설정한 뒤,
모든 dp[i]값들을 -1 로 두었습니다.
이후 dp[0] = 0 , 즉 아무것도 담지 않았을 때 가치는 0 이라고 둔 뒤,
모든 물품들을 차례로 보며 dp 값을 최신화 해 주었습니다.
예를 들어 물품 A = <w1, v1> : <A무게, A가치> 를 본다고 할때,
이전 dp[i] 값들을 보며
(1) i+w1 <= K 일때 ; 즉 무게 i + A무게가 제한 중량 K 이하일때,
(2) dp[i] != -1 일때 ; 즉 i만큼 담은 가치가 있을 때,
(3) dp[i+w1] < dp[i] + v1 일때 ; 즉 기존 dp[i+w1]의 가치보다 dp[i]+A의가치가 클 때,
를 만족하면 dp 값을 갱신해 주었습니다.
안녕하세요~~! 좋은 풀이 감사합니다!
답글삭제한 가지 의문이 있는데,
for (int i = 0; i < K; ++i){
if(i+W<=K){
if(dp[i]!=-1 && dp[i+W]<dp[i]+V){
temp[i+W] = dp[i]+V;
TT.push_back(i+W);
}
}
else break;
}
여기서 바로 dp를 갱신하지 않고 temp를 거쳐서 갱신하는 이유가 무엇인가요?
다음과 같이 바로 dp를 갱신하면 답이 틀리던데, 그 이유가 궁금합니다 ㅠ
for (int i = 0; i < K; i++) {
if (i + W <= K) {
if (dp[i] != -1 && dp[i + W] < dp[i] + V) {
dp[i + W] = dp[i] + V;
}
}
else
break;
}
안녕하세요. 질문 감사드립니다.
삭제바로 dp 값을 최신화 하는 경우 결론부터 말씀드리자면 같은 물건을 여러번 넣게 됩니다.
때문에 temp를 거쳐 dp 값을 최신화 하여, 이와 같은 중복을 피하고자 하였습니다.
예를 들어
input:
3 5
1 2
3 3
4 5
outpt:
정답 : 7
오답 : 10
이 됩니다.
정답은 1 , 4 를 넣어 2, 5 의 가치를 얻은 2+5 = 7 이지만,
dp 값을 바로 최신화 되는 경우 1을 5개 넣어 10의 가치라는 오답이 나오게됩니다.
도움이 되시면 좋겠습니다!