[백준] No.12865 - 평범한 배낭 (C++, 배낭 문제)

문제

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

풀이

DP의 유형 중에서도 배낭 문제(Knapsack)의 대표 문제이다.

 

해당 유형의 문제를 풀기 전에는 배낭 알고리즘을 공부하고 풀어보는 것을 추천한다.

 

배낭 알고리즘은 여러 물건 중에서 특정한 조건을 만족시키는 조합을 구하는 문제들에 적용이 가능하다. 

 

위의 문제에서  우리는 물건들 중에서 최대 무게를 넘지 않는 가치의 최댓값을 구해야 한다.

 

단순히 생각하면 dp[]배열에 해당 무게(wight)에서의 최대 가치를 구하는 점화식을 생각할 수 있다.

dp[weight] = max( dp[weight - 선택한 물건의 무게] + 물건의 가치);

 

하지만 같은 무게이지만 가치가 다른 경우 문제가 발생한다.

 

무게가 3으로 같지만 가치가 5와 10으로 다른 경우를 생각해보자.

dp[3]은 두 물건 중 가치가 큰 10으로 값이 저장된다.

이후 dp[6]을 계산할 때 물건의 가치가 큰 것을 선택한 것으로 값이 저장되기 때문에 가치가 10인 물건이 다시 한번 선택되어 중복 선택이 발생한다.

 

이러한 경우는 배낭 알고리즘을 사용하면 쉽게 배제 가능하다.

일단 물건들은 순서(idx)를 갖도록 정렬한다.

바로 현재의 무게(weight) 해당 물건(idx)를 선택하거나 선택하지 않는 두 가지 방법 중 더 큰 값을 저장하는 것이다.

 

1. 선택하는 경우: dp[weight - idx.무게][idx-1] + idx.가치

선택한 무게만큼 현재 무게에서 빼주고 가치는 더해준다.

 

2. 선택하지 않는 경우: dp[weight][idx-1]

선택하지 않고 바로 가치도 더해주지 않는다.

 

두 값 중 더 큰 값이 dp[weight][idx]의 값이 된다.

 

dp[weight][idx] = max( dp[weight - idx.무게][idx-1] + idx.가치, dp[weight][idx-1])

코드