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

Solution:

You'll need width of stretcher bars to calculate length for angles (spending additional2*$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
Copy code

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