DP와 그리디 알고리즘 구분하기

똑같이 가방에 담은 물건의 최대 비용을 구하는 문제라고 해보자.

만약 해당 문제가 그리디 알고리즘으로 설계되었다면 순서가 존재하고, 매 시점마다 고를 수 있는 물건과 없는 물건이 구분될 것이다. 위의 일차별로 최대 비용 물건을 뽑아서 결국 종합 최대 비용을 구하는 문제는 매 일차마다 최선의 물건을 선택해 나가야 하므로 그리디 알고리즘이다.
반면 DP는 선택에 순서가 없다. 대표적인 DP인 배낭 문제처럼 가방의 용량 내에 최대 비용이 되도록 담기만 하면된다.