[다이나믹] BOJ#12865 - 평범한 배낭

[ye-yo]

⚠️ 나의 풀이

❗️ 오답 원인 분석

• 기존 물건들의 무게 합을 알아야 현재 물건을 넣을지 말지 계산이 가능하기 때문에 배낭의 무게 별로 1부터 K까지 계산했어야 함
  => 메모이제이션 할 대상이 무엇인지 생각해보기!

🔑 풀이 핵심

배낭에 담을 수 있는 무게가 1일 때의 가치 합, 2일 때의 가치합 ....을 메모이제이션해서 계산하는 것이 핵심!

for (int i = 1; i <= N; i++){ // 물건 개수만큼 반복
  for (int j = 1; j <= K; j++){ //배낭 무게만큼 반복
    배낭 용량이 j일 때 i번째 물건까지의 가치 최대값은?
    if(물건의 무게 > 가방 용량 ) 배낭 용량이 j일 때 i-1 물건까지의 가치 최대값
    else
      1) i번째 물건을 담을 경우 vs 2)담지 않을 경우
  }
}

1) i번째 물건을 담는 경우

배낭에 물건을 넣는다. :이전 물건까지 탐색했을 때의 배낭 + V[i]
= DP[i-1](i-1까지의 배낭의 가치합) + V[i]

*하지만 넣었을 때 배낭 용량이 초과될 수 있음
= (배낭 용량 - 물건 무게 ) 만큼의 용량을 가지는 배낭 + V[i]
= DP[i-1][j-W[i]]
(현재 물건을 넣어야하니까 그만큼의 무게를 빼고, 뺀 무게일 때의 가치값으로 계산해야 함)

2) i번째 물건을 담지 않는 경우

이전 물건까지 탐색했을 때의 배낭 가치합
DP[i-1][j]

DP[i][j] = max(DP[i-1][j-W[i]] + V[i], DP[i-1][j])