Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


smekla
Posts:
7
Registered:
1/20/07


what algorith to use for this task?
Posted:
Jan 22, 2007 9:46 AM


hello!
i have a task:
Given: many rectangular shapes with the same measurements (length and width) and many smaller size rectangular shapes, that are given like this: a(1), b(1), k(1); ...; a(n), b(n), k(n) here a(i)  is shape width, b(i)  is shape height, k(i)  is the number of how many same size figures do we need.
Requirements: to cut all the figures using the least number of shapes as possible. When cutting, figure sides have to be parallel to shape sides.
For example, we need to make a set of furniture for the kitchen. the figures of that set are rectangles (or other but approximated as rectangles). We need to use the least number of shapes.
can anybody tell me what algorithm i have to use to solve this task? help please!
best regards, smekla



