동적 계획법 (Dynamic Programming)

겹치는 부분문제를 표로 저장해 푸는 정확 기법.

다른 이름: Dynamic Programming · DP · 동적 프로그래밍

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

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목으로 들어오는 관계 4

사용 방법
2D 배낭 (직사각형)에서 동적 계획법 (Dynamic Programming)로
2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법
길로틴 절단에서 동적 계획법 (Dynamic Programming)로
길로틴 패턴은 재귀적 분할 구조 덕분에 동적 계획법으로 효율적으로 다룰 수 있다(Gilmore–Gomory).
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions
  서지정보
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
사용 방법
0/1 배낭 문제에서 동적 계획법 (Dynamic Programming)로
0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법
팔레트 적재에서 동적 계획법 (Dynamic Programming)로
제조사 팔레트 적재의 정확/구성적 접근은 재귀적 분할과 동적 계획법으로 보고되어 왔다.
증거C · 벤더 / 사례 보고
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
사용 방법 2D 배낭 (직사각형)에서 동적 계획법 (Dynamic Programming)로	2D 배낭 변형은 동적 계획법 및 그 위에 구축된 정확·근사 방법으로 다뤄져 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법 길로틴 절단에서 동적 계획법 (Dynamic Programming)로	길로틴 패턴은 재귀적 분할 구조 덕분에 동적 계획법으로 효율적으로 다룰 수 있다(Gilmore–Gomory).	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions 서지정보 Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
사용 방법 0/1 배낭 문제에서 동적 계획법 (Dynamic Programming)로	0/1 배낭 문제는 의사다항(pseudo-polynomial) 동적 계획법으로 정확히 풀 수 있다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
사용 방법 팔레트 적재에서 동적 계획법 (Dynamic Programming)로	제조사 팔레트 적재의 정확/구성적 접근은 재귀적 분할과 동적 계획법으로 보고되어 왔다.	C · 벤더 / 사례 보고	—	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.