[JAVA] 백준 12865번 평범한 배낭

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

12865번: 평범한 배낭

DP를 이용해서 푸는 문제이다.

풀면서 한번 틀리고, 찾았던 반례에 대해서 적어보려고 한다.

배열 d는 인덱스값을 무게로 하고, 그 무게에서 가질 수 있는 최대값을 최대 가치 값(원하는 답)으로 둔 변수이다.

최대로 가질 수 있는 무게(K)가 7이라고 해보자.

 

무게(W)가 4이고 가치(V)가 8이라고 하면,

d[4]에서 가질수 있는 최대값은 8이고, d가 인덱스 5,6,7에서도 가질수 있는 무게의 최대값은 8이다.

 

무게가 6이고 가치가 9라고 한다면,

d[4],d[5]에서 가질 수 있는 최대값은 8, 무게 d[6],d[7]에서 가질수 있는 최대값은 9가 된다.

 

무게가 3이고 가치가 3 이라면, 

d[3]은 3, d[4], d[5]가 가질수 있는 최대값은 8,

d[6]이 가질수 있는 최대값은 9, d[7]이 가질수 있는 최대값은 d[4]와 d[3]을 합친 11이 된다.

 

위 로직을 이용하여 문제를 풀면서 18번 줄에 j=0; j<=k; j++로 설정했었는데 틀렸었다.

반례를 찾아보니 아래와 같은 반례가 있었다.

8 6
6 12
6 13
4 8
4 7
3 7
5 13
5 11

 

j값을 0부터 시작하면, 자기 값을 두 번 계산하게 되는 오류가 발생한다.

예를들어서 d[3]의 최대값이 7이 되는 순간을 보면,

d[6]의 최대값을 구하는 방법이 Math.max(d[3] + [무게가 3인 배낭의 가치], d[6])으로 하면

d[3]에 최대박 7을 넣어주고, d[6]에서 7값을 중복으로 더해주는 경우가 발생하게 된다.

 

따라서, 무게가 W인 경우 d[W이상의 값부터 최대값 K까지] 의 범위에서 가치가 최대값인 경우를 구하기 위해서는 W값부터 K값까지 올라가면서 구하는 것이 아니라 K값부터 W값까지 내려오면서 구해야 한다.