냅색 알고리즘의 의미와 메모이제이션 활용

Question

안녕하세요. 냅색 알고리즘에 대해 질문있습니다.

이렇게 보석을 하나씩 늘려가면서 값을 계속 갱신하는 것이 냅색 알고리즘인가요?

추가로, 이번 문제를 보면 dy[]의 값을 바꾸어주는 경우가 많은데, 여기에서 메모이제이션을 활용할수는 없는지 궁금합니다.

감사합니다.

Answer

안녕하세요^^

네. 맞습니다. 하나 하나 늘려가면서 적용하는게 냅색입니다.

어찌보면 다이나믹은 기록된 값보다 더 좋으면 바꾸고 아니면 그대로 두는 것이기 때문에 그 자체로 메모이제이션을 활용하고 있다고 봅니다.