[동적 계획법] [시도X] SUSHI 회전 초밥

1. 완전 탐색

 

이 문제는 packing 문제에서

중복가능한점을 제외하고 전부 같다

 

따라서 이문제는 다음과 같이 쓸수있다.

 

menu(price) = price로 시킬 수 있는 메뉴의 최대 선호도

 

이에 모든 메뉴를 for문으로 탐색하면서

price를 넘어가지 않도록 선택하는 재귀함수를 구현하면 

답을 구할 수 있다.

 

2. 반복적 동적 계획법

 

하지만 이 문제의 price의 최대 값은 10억이다.

총 n메뉴가 있을때 값이 2만을 넘지 않으므로

n^50000시간 이상 걸릴 수 있을 것이다. 

 

이렇게 큰 수를 메모이제이션 하려면, 슬라이딩 윈도 기법을 사용해야한다.

이 기법은 반복적 동적 계획법을 이용해야만 쓸 수 있다.

 

menu(price) = price로 시킬 수 있는 메뉴들의 최대 선호도 합

 

이 식이 의미하는 바는 

price 가 0일때 부터 m 까지 순서대로 탐색하면서

어떤 메뉴들을 살 수 있을 때 

메뉴의 가격을 price에 서 뺀 값

즉, menu(price - item[].price) 에서 해당 메뉴의 선호도를 더한 값

이 최대인 메뉴를 고르는 것과 같다.

 

menue(price) = MAX( menue( price - item[i].price) + item[i].pref)

(-1 < i < n )

 

 

이 점화식으로 부터 반복적 동적 계획법으로 함수를 구현하는것은 간단하다.

 

하지만 price가 최대 10억까지인것은 변함이 없다.

그러므로 문제에서 주어진 제한 조건을 잘 써먹어야한다.

 

문제에서는 메뉴의 가격이 항상 100의 배수이고 20000원 이하라고 주어졌다.

 

이를 통해 예산은 1000만까지 줄일 수 있고, 메뉴가 200원 이하로 줄일 수 있다.

 

또한 price 가 0 -> m 로 탐색할 때

price - item[i].price 에서 결국 200 이하의 값들만 쓰인 다는 것을 알 수 있다.

그리고 한번 업데이트 된 값은 업데이트 이전의 값을 필요로하지 않는다.

 

그러므로 price를 201으로 나눈 나머지 값으로만 메모이제이션을 할 수 있고,

이를 통해 메모리를 아낄 수 있다.

 

 

 - 알고리즘 문제해결전략 359p