2D Knapsack
Select a subset of rectangles for a single sheet, maximizing value (or area).
Also called: 2D Knapsack · Rectangle knapsack · 직사각형 배낭
Last verified: 2026-05-27
Definition
Choose a subset of candidate rectangles and place them, without overlap, on a single fixed-size sheet, maximizing the total value (often area) of the placed pieces.
Example
Suppose a sheet and candidates (value 9), (value 4), (value 3), and (value 4). Choosing the first three — at the bottom-left, along the top row, in the right column — tiles the sheet exactly for value . Adding the would exceed the sheet area, so this trio is optimal.
Family
A core orthogonal cutting & packing problem alongside bin packing and strip packing. Its "what to include" selection structure on a single sheet shares its name and structure with the one-dimensional 0/1 Knapsack Problem.
Related nodes
See the depth-1 graph below.
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| uses methodDynamic Programming | 2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it. | — | B |
|
| direct benchmark2DPackLib | 2DPackLib includes two-dimensional orthogonal knapsack instances. | — | A |
|
| shares method with2D Bin Packing | 2D knapsack and bin packing share the orthogonal placement core and many exact/heuristic methods. | E2 | B |
|
| generalizes0/1 Knapsack Problem | 2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement. | E2 | B |
|
| uses methodBranch and Bound | Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004). | — | A |
|
| uses methodGenetic Algorithm | 2D knapsack variants have also been addressed with metaheuristics such as genetic algorithms. | — | B |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
See also
Not directly linked, but conceptually close — by the connections and descriptions they share.
- 2D Irregular NestingFormal problem4 connections in common
- 3D Bin PackingFormal problem4 connections in common
- 1D Cutting StockFormal problem4 connections in common
- Integer Linear ProgrammingMethod4 connections in common
- Column GenerationMethod3 connections in common
- Lower BoundsMethod2 connections in common