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):
When that's not the case, there's a solution that divides the shape vertically (into two subproblems):________ ________ | |____ | |____ ______| | ______| | | | | | ____| | => ____| subproblem | | | |_________________________| | | | a single strip | |_________________________| |_________________________|
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):________ ________ | |____ | |____ ______| | ______| | | | | | | ____| | => ____| | | | | | | subproblem | | | | subproblem| | |_________________________| |___________|_____________|
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) ..________ ________ | |____ |________|____ ______| | ______| | | | NEVER! |______|_____________| ____| | => ____|____________________| | | |___________| | | | | |_____________| |_________________________| |___________|_____________|
Output: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); } }
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.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
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)
In reply to Re: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by blokhead
in thread Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by doowah2004
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |