동적 계획법 (Dynamic Programming)

문제를 부분문제로 나눠 각 부분문제를 한 번만 풀고 표에 저장(메모이제이션)해 정확해를 쌓아 올리는 기법. 0/1 배낭 문제는 남은 용량을 상태로 하는 의사다항(pseudo-polynomial) DP로 풀리고, 길로틴 절단의 재귀적 분할 구조도 DP(Gilmore–Gomory의 다단계 재귀)와 잘 맞는다. 다만 입력 개수 가 아니라 수치(용량·치수)에 비례하므로 값이 크면 비싸질 수 있다.