# php - Framing painter's canvases (optimization or AI?)

184

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.

643

#### Solution:

You'll need width of stretcher bars to calculate length for angles (spending additional`2*\$stretcher_width` for each side of canavas)

``````use strict;
use warnings;

my \$stretcher_length = 200;
my \$stretcher_width = 0;
my \$wasted_per_side = 2*\$stretcher_width;
my @sc = (
{w=> 25,  h=> 35, pcs=> 20},
{w=> 50,  h=> 30, pcs=> 30},
{w=> 90,  h=> 50, pcs=> 40},
{w=> 110, h=> 60, pcs=> 25},
);
# all possible bars needed from longest to shortest
my @all = sort { \$b <=> \$a } map {
(
(\$_->{w}+\$wasted_per_side) x2, (\$_->{h}+\$wasted_per_side) x2
)x \$_->{pcs};
}
@sc;

# lets cut from 200cm bars
my @rest;
for my \$len (@all) {

my \$cut_from;
# do we already have bar which can be used?
for my \$len_have (@rest) {
# yes, we have
if (\$len_have >= \$len) { \$cut_from = \\$len_have; last; }
}
# no, we need another 200cm bar
if (!\$cut_from) {
print "Taking new \$stretcher_length cm bar\n";
push @rest, \$stretcher_length;
\$cut_from = \\$rest[-1];
}
# cut it
print "Now you have at least one bar \$\$cut_from long and cut away \$len\n";
\$\$cut_from -= \$len;

# keep @rest bars sorted from shortest to longest
@rest = sort { \$a <=> \$b } @rest;
}

print scalar @rest;
# print "@rest\n"; # left overs
``````
566

#### Solution:

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

People are also looking for solutions to the problem: php - remove amount from price then insert new price

Source