DP로 문제를 풀기 위해서는 2가지 전제조건이 필요하다.
아래의 예시를 통해 설명한다.
https://s3-us-west-2.amazonaws.com/secure.notion-static.com/7a7a2458-4434-4dba-a520-b1e02b2d80ad/p11450.pdf
아주 간단하게 요약을 한다면 필요한 의복의 종류를 하나씩 사면서 가장 많은 예산을 소비하는 경우의 예산을 구하는 문제이다. 이를 여러 접근법으로 풀어보고 나서 DP로 풀어보자.
예산을 최대한 사용하는 것이 목표이므로, 떠올릴 수 있는 그리디 아이디어 중 한가지는 각 예복 g마다 가장 비싼 품목을 예싼 범위 안에서 구매하는 것이다. (그리디로 푸는 방법이 이것만 있는 것은 아니다. 그러나 그 또한 WA를 받을 것이다.).
이 방법은 처음부터 너무 높은 가격의 품목을 골라 나중에 돈이 부족해 질 가능성이 높으므로 대부분의 TC에서 동작을 하지 않는다.
이 문제를 분할 정복을 이용해서 풀 수는 없다. 왜냐하면 부분 문제(다음의 브루트 포스 항목에서 설명된다.)가 서로 독립적이지 않기 떄문이다. 따라서 분할 정복을 이용해서 각각을 독립적으로 푸는 것은 불가능하다.
다음으로 Complete Search( or Backtracking)을 이용하여 이 문제를 풀 수 있는지를 살펴보자. 이 문제에 backtracking을 사용하기 위해 shop(g, money)함수를 하나 만들자.
먼저 money = M, 그리고 g = 0으로 두고 시작한다. 그리고 나서 g = 0 번 garment에 대해서 가능한 모든 품목을 시도해본다(품목은 최대 20가지일 수 있다). 만일 i번 품목을 선택헀다면, i번 품목의 가격을 money에서 빼주고, 재귀를 이용하여 g = 1번 예복(이 역시 최대 20가지이다.)에 대해 같은 과정을 계속 반복해나간다. 이후의 작업 또한 마찬가지이다. 마지막 g = c-1 번 예복에 대한 품목을 선택하고 나면 진행을 멈춘다. 만일 그전에 money < 0 이된다면 불가능한 해를 가지치기하면 좋다. 가능한 모든 조합을 시행해보고 그 중에서 money의 값이 음수가 아니면서 최소가 되는 경우를 선택한다. 이 과정을 아래와 같이 점화식의 형식으로 정의한다.