Dynamic Programming

Exact technique that stores overlapping subproblems in a table.

Also called: Dynamic Programming · DP · 동적 프로그래밍

An exact technique that breaks a problem into subproblems, solving each once and storing it in a table (memoization) to build the optimum. The 0/1 Knapsack Problem is solved by pseudo-polynomial DP with remaining capacity as the state, and the recursive subdivision of Guillotine Cutting fits DP (the Gilmore-Gomory multistage recursion) too. Because it scales with the numeric values (capacity, dimensions) rather than the item count, large values can make it expensive.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships to this entry 4

uses method
2D Knapsack to Dynamic Programming
2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method
Guillotine Cutting to Dynamic Programming
Guillotine patterns, thanks to their recursive subdivision structure, can be handled efficiently with dynamic programming (Gilmore–Gomory).
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions
  Citation details
  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.
uses method
0/1 Knapsack Problem to Dynamic Programming
The 0/1 knapsack problem can be solved exactly by pseudo-polynomial dynamic programming.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method
Pallet Loading to Dynamic Programming
Exact/constructive approaches to manufacturer's pallet loading have been reported with recursive partitioning and dynamic programming.
EvidenceC · Vendor / case-reported
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Knapsack to Dynamic Programming	2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method Guillotine Cutting to Dynamic Programming	Guillotine patterns, thanks to their recursive subdivision structure, can be handled efficiently with dynamic programming (Gilmore–Gomory).	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions Citation details 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.
uses method 0/1 Knapsack Problem to Dynamic Programming	The 0/1 knapsack problem can be solved exactly by pseudo-polynomial dynamic programming.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method Pallet Loading to Dynamic Programming	Exact/constructive approaches to manufacturer's pallet loading have been reported with recursive partitioning and dynamic programming.	C · Vendor / case-reported	—	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.