[백준 / #12865 / C++] 평범한 배낭

역시 학교 수업은 제대로 들어야겠다는 교훈을 얻은 알고리즘이다. 문제해결기법이라는 강의가 있었는데 그 강의 시간에

 

교수님께서 설명해주신 방법대로 풀면 바로 풀리는 쉬운 문제였다. 물론 처음에는 조금 돌긴 했지만 이내 금방 길을 찾을

 

수 있었다.

 

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

12865번: 평범한 배낭

 

이 문제는 익히들 알고 있을 수도 있고 유명한 knapsack problem이다. 그런데 이제 변형이 없고 그냥 문제 제목 그대로 평

 

범한 배낭 문제이다. 거두절미하고 문제 해석으로 들어가보자.

 

 

문제 해석:

 

 

이 문제는 여러 방면으로 풀 수 있다. 우선 주어진 시간은 2초로 조금은 넉넉한 편이다. 자료의 최대 크기가 100,000으로 조

 

금은 조심해야 할 필요가 있는 문제이다. 준서가 가지고 있는 물품 들에는 무게와 가치가 있는데 준서가 최대로 들고 갈 수

 

있는 무게는 k이다. N개의 물건들 중에 무게 k를 넘지 않는 선에서 최대한의 가치로 들고 가야 하는 문제이다.

 

 

여기까지 봤을 때 모든 경우의 수를 탐색하여 제일 큰 값을 출력하면 되겠다! 백트래킹을 사용하면 되겠군 하여 사용했다가

 

대차게 시간초과가 나버렸다 ㅋㅋㅋㅋ 물론 내 코드가 최적화도 덜 되어있고 하다보니 성능이 안좋아서 시간초과가 났을

 

수도 있으나 일단 이 문제는 N의 값이 최대 100이라는 작은 숫자이기 때문에 다른 알고리즘을 생각해보기엔 충분했다.

 

Branch-and-Bound를 사용할까 생각해보았지만 백트래킹과 크게 차이가 없을 것이라 생각해서 코드를 짜보진 않았으나

 

지금 생각해보니 가능도 할 것 같다. 하지만 나는 동적계획법(Dynamic programming)을 사용했다.

 

 

 

알고리즘 해설 및 코드:

 

 

코드를 보자.

 

 

솔직히 말하자면 무게와 가치를 각각 저장하고 있는 w_v벡터를 정렬하여 계산하고자 했지만 실행 시간에 유의미한 차이는

 

없는것 같아 정렬하지 않고 계산하였다. 우선 첫번째 물건에 대해 dp 테이블의 [ 0 ] 행의 값을 정해준다. 여기서 행은 각 물

 

건의 인덱스, 즉, 각 물건의 순서(각각의 물건)을 뜻하고 열은 k까지의 무게를 뜻한다. 이게 어떻게 이렇게 되냐 하면 두개의

 

물건을 합해서 k값에 딱 맞는 무게가 될 수도 있고 k 값보다 조금은 작은 값이 될 수도 있다.

 

 

이제 dp 테이블을 채우고 사용하는 방법이다. 우선 만약 m값이 현재 계산 중인 물건의 무게보다 크거나 같으면 이 물건을

 

챙길 수 있다는 의미이다. 이 때, 그 전의 물건 값을 이용하여 이 값을 계산해본다. 만약 그 전의 물건을 챙겼을 때보다 이

 

물건을 챙겼을 때 물건의 가치가 더 크다면 현재의 물건을 취한 값을 적어준다. 이러한 비교 과정이 필요하기 때문에 첫번

 

째 줄을 채워주었다. 그리고 만약 현재의 물건과 과거의 물건의 무게를 합해서 m값이 된다면 그 물건의 가치값과 현재 물

 

건의 가치값을 더한 값이 그 전 물건만을 취했을 때의 값보다 크면 가치 값을 교체해주고 그렇지 않다면 그 전의 가치값을

 

그대로 복사해온다. 이렇게 dp테이블의 그 전 값을 이용해나가며 최댓값을 저장하고 계속해서 갱신해준다. 그러면 결국에

 

는 최댓값이 ans 변수에 남게 된다.

 

 

말로 풀어쓰려니 상당히 빙빙 돌아가고 글이 이해가 되려나 싶지만 코드를 보면 아마 단박에 이해가 될 것이다.

 

추가로 다 풀고나서 구글링을 조금 해보니 1차원 배열로 푸는 방법도 있는것 같다. 구글링하면 금방 나오니 흥미가 있다면

 

찾아보길 바란다.