in reply to Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.

You are a bit unclear about what to do when you can't match the shape exactly. What should be minimized? The difference in area between the desired pyramid and the constructible pyramid? My advice that follows will still apply in the approximate case, but I only give code that solves the case where you can build the shape exactly.

This problem can be solved with straight-forward dynamic programming. Faced with building this desired shape, consider any solution. Either there's a solution that includes a long strip that covers the whole length of the bottom (then the top becomes another subproblem):

________ ________ | |____ | |____ ______| | ______| | | | | | ____| | => ____| subproblem | | | |_________________________| | | | a single strip | |_________________________| |_________________________|
When that's not the case, there's a solution that divides the shape vertically (into two subproblems):
________ ________ | |____ | |____ ______| | ______| | | | | | | ____| | => ____| | | | | | | subproblem | | | | subproblem| | |_________________________| |___________|_____________|
Since you only are doing only pyramid shapes, you can convince yourself that if there's a solution, there's a solution that decomposes in the manner I just described. You will never have a case where you need a solution that looks like this (i.e, it doesn't have just a single strip at the bottom and is not split vertically):
________ ________ | |____ |________|____ ______| | ______| | | | NEVER! |______|_____________| ____| | => ____|____________________| | | |___________| | | | | |_____________| |_________________________| |___________|_____________|
Now, to just formulate this as a dynamic programming algorithm. You say you want the "simplest" pyramid, but you need some way to measure "simplicity". For my code below, I just chose to minimize the number of strips. (I had to change your example shape so that an exact fit was possible, and use integers to avoid floating-point rounding errors) ..

use List::Util qw(min sum); use strict; use Memoize; memoize 'solve'; my @thicknesses = (4, 8, 16, 24, 32, 47, 64); my @goal = ( [10,20], [15,28], [20,48], [10,40] ); sub argmin(&@) { my $i = undef; my $min = undef; my $block = shift; for (@_) { my $this = $block->($_); if ( not defined $min or $min > $this ) { $min = $this; $i = $_; } } return wantarray ? ($i, $min) : $i; } my @decomp; my $INFINITY = 1e10; sub solve { my ($left, $right, $height) = @_; ## we could either we can split into two pyramids.. my ($split_index, $split_value) = (undef, $INFINITY); if ($left != $right) { ($split_index, $split_value) = argmin { solve($left, $_, $height) + solve($_+1, $right, $height) } $left .. $right +-1; } ## ... OR we could try to place a strip across the whole length my $min_height = min map { $_->[1] - $height } @goal[$left .. $rig +ht]; my @strips = grep { $_ <= $min_height } @thicknesses; ## (degenerate case, nothing left to do!) return 0 if $min_height == 0 and $left == $right; my ($strip_size, $strip_value) = (undef, $INFINITY); if (@strips) { ($strip_size, $strip_value) = argmin { 1 + solve($left, $right, $height+$_) } @strips; } ## which one of these is best? if ($strip_value < $split_value) { $decomp[$left][$right][$height] = [ strip => sum( map { $goal[$_][0] } $left .. $right ), $strip_size ]; return $strip_value; } else { $decomp[$left][$right][$height] = [ split => $split_index ]; return $split_value; } } printf "you can solve this with %d strips\n", solve(0, $#goal, 0); reconstruct(0, $#goal, 0); sub reconstruct { my ($left, $right, $height) = @_; my $how = $decomp[$left][$right][$height]; return if not ref $how; if ($how->[0] eq "strip") { print "strip of length $how->[1], height $how->[2]\n"; reconstruct($left, $right, $height + $how->[2]); } else { my $split = $how->[1]; reconstruct($left, $split, $height); reconstruct($split+1, $right, $height); } }
Output:
you can solve this with 5 strips strip of length 55, height 16 strip of length 25, height 4 strip of length 15, height 8 strip of length 20, height 32 strip of length 10, height 24
Basically what we do is, check to see if we can split the shape into two parts vertically, and find the split that is best (recursive subproblems). Then what sizes of strips (if any) we can lay down across the whole length of the bottom, and find the best strip (recursively). Then just return which of these choices gave the better value (and store how you got that value, so you can reconstruct the solution). And of course, we memoize to avoid computing the same subproblem twice. All in all, this is a pretty typical way to build a dynamic programming algorithm. They are a good tool to really understand.

Again, this only is correct (well, I hope it's correct) when you can build the shape exactly. It's nontrivial, but not too difficult, to modify this algorithm to do approximate matching, once you specify what you want to optimize. But I think I've already spent enough time on this for one afternoon ;)

blokhead (my 400th node)

  • Comment on Re: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
  • Select or Download Code

Replies are listed 'Best First'.
Re^2: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by tilly (Archbishop) on May 04, 2005 at 07:55 UTC
    You may be able to convince yourself, but I'm convinced that you're wrong about that decomposition being possible. Let me try to convince you.

    Consider the case where you have blocks with width/thickness pairs of 4,3, 1,5 and 3,2. They can be arranged into the following pattern to form a 5,8 square:

    _______ _ | | | | | | |_______| | | | | | | |_____|_| | | | | | | |_|_______|
    (I've actually drawn each horizontal space as 2 characters...)

    I assert that that example can't be broken down as you claimed it could. A brute force proof is fairly straightforward. You have to put some block in the top left corner. Let's examine each possibility.

    • Top left is a 4,3 block. Then going clockwise looking at width and depth it is easy to show you need a 1,5, then a 4,3, then a 1,5 leaving the 3,2 hole in the middle. (This is the diagram above.)
    • Top left is a 1,5 block. Going counter-clockwise it is easy to see that you need a 4,3 then 1,5 then 4,3 leaving a 3,2 hole in the middle. (This is the mirror image of the diagram above.)
    • Top left is a 3,2 block. Going clockwise we need it 2 wider, so we have to add 2 1,5s. To add 3 to the depth below them you need a 4,3, and then to the left of that we have to add 1 more width so we need a 1,5 that unfortunately intersects our original 3,2 block. This case is therefore impossible.
    So you see that by brute force there are 2 ways to solve this problem, and neither decomposes as you'd hoped.
Re^2: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by doowah2004 (Monk) on May 03, 2005 at 18:19 UTC
    Thanks Blockhead,
    I will take a look at this and see what I can do.