0

Given a number N of rectangular kitchen worktops, of variable dimensions to be cut from slabs of material of fixed dimensions

Determine an optimal fit to minimise wastage and number of slabs used.

Two refinements to the problem are: 1. Slabs may be of variable dimensions 2. The worktops may additionally have rectangular "cutouts" e.g. for a sink. A Cutout may be considered as a Slab

Andrew Bingham
  • 1
  • I haven't studied much of computational complexity, but this sounds to me like it's NP-hard, and the desicion problem "can you cut the $N$ worktops with only $M$ slabs?" sounds NP-complete (this problem is very similar to the knapsack problem, which does have these properties). If this is true, then something that is significantly better than trial-and-error is quite literally a milion-dollar algorithm. – Arthur Jun 26 '15 at 11:35

1 Answers1

0

This problem is NP-complete: https://en.wikipedia.org/wiki/Cutting_stock_problem

It might be harder, due to the possibility of cutouts.

Michael Tiemann
  • 524