php - Framing painter's canvases (optimization or AI?)
Here is a problem that I wld like to formulate: The painter intends to frame his square canvases of different sizes in centimeters:
25cm x 35cm -- 20 pcs, 50 x 30 -- 30 pcs, 90 x 50 -- 40 pcs, 110 x 60 -- 25 pcs,
The painter will purchase wooden stretcher bars of 200cm and cut them accordingly. Condition is "each frame edge should be single continuous bar. No gluing".
Unlimited wooden stretcher bars available in length 200 cm. how many bars of (200 cm) the Painter should buy? How to calculate the optimized number of bars, with least wastage of bars?
Is this problem related to optimization (mathematical programming) or AI? PHP, Perl, vbscript codes welcome.
============== For clarification purpose, here are the exact lengths to be produced from 200cm bars.
LENGTH PIECES TOTAL LENGTH 110 cm 50 pcs 5500 cm 90 cm 80 pcs 7200 cm 60 cm 50 pcs 3000 cm 50 cm 140 pcs 7000 cm 35 cm 40 pcs 1400 cm 30 cm 60 pcs 1800 cm 25 cm 40 pcs 1000 cm =========================================== ALL TOTAL: 26900 cm
it is equal to 134.5 bars, if we were allowed to glue small remaining pieces.
It will be practical to guide the painter what lengths should be cut from each bar. Otherwise he will not know what to do with the bars supplied.
You'll need width of stretcher bars to calculate length for angles (spending additional
2*$stretcher_widthfor each side of canavas)
it is actually cutting stock problem Wikipedia article
There is a C implementation CPSOL Solves above problem with 135 sticks.
Unfortunately, failed to find a Perl implementation