최적화 문제 동적 계획법 레시피, 배낭 문제(냅색 문제)

[최적화 문제 동적 계획법 레시피]

1. 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탄색 알고리즘을 설계한다.

2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.

3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄어들면 줄어들수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있다.

4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 한다.

5.메모이제이션을 적용한다.

 

[배낭 문제 레시피]

몇 개의 물건이 있고 각 물건에는 무게와 가치라는 2개의 매개 변수가 주어진다. 일정한 무게까지 물건을 배낭에 넣을 수 있다고 할 때 가치의 합계가 최대가 되려면 물건을 배낭에 어떻게 넣어야 할까?

1. 탐색 이용

2. 메모화 재귀 사용

3. 동적 계획법

 

1. 각각 물건에 대해 '산다'와 '사지 않는다'를 기준으로 나눈다. 깊이 우선탐색으로 푼다.

2. 총 무게와 몇 번째 물건까지 고려했는가? 라는 2개의 요소로 가치 합계의 최댓값을 저장한다.

다양한 관점에서 문제를 바라보는 것이 동적 계획법을 마스터하는 첫 걸음이다.