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.

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 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};

# 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



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


Didn't find the answer?

Our community is visited by hundreds of web development professionals every day. Ask your question and get a quick answer for free.

Ask a Question

Write quick answer

Do you know the answer to this question? Write a quick response to it. With your help, we will make our community stronger.

Similar questions

Find the answer in similar questions on our website.