Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.

by mstone (Deacon)
on May 03, 2005 at 22:40 UTC ( [id://453766]=note: print w/replies, xml ) Need Help??


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

To follow up blockhead's advice about dynamic programming, you might also want to look at greedy algorithms.

A greedy algorithm breaks a problem down into recursive subproblems just like dynamic programming does, but it picks the best solution at each level before moving on to the subproblem. It's like making change for 47c. A quarter is the largest coin that fits in a 47c 'hole'. That leaves 22c. A dime is the largest coin that fits in a 22c 'hole'. That leaves 12c. By the same process, we get another dime and two pennies.

Greedy algorithms perform well on average, but they do not guarantee an optimal solution every time. If we tried the above experiment with coins worth 35c, 30c, and 15c, the greedy algorithm would tell us that a single 35c coin is the best match. But in fact, a 30-15 combination would get us closer to 47c.

If you want to guarantee an optimal solution, you need to use dynamic programmming. If you're willing to tolerate imperfect solutions, or you know that your pieces are partitioned well enough to solve any problem, you can use greedy algorithms.

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

Replies are listed 'Best First'.
Re^2: Finding the simplest combination of descrete thicknesses that sums nearest to the target thickness.
by doowah2004 (Monk) on May 05, 2005 at 15:02 UTC
    Thanks mstone, Looking at the discreet thicknesses: 0.4, 0.8, 1.6, 2.4, 3.2, 4.7, 6.4, All of these (save 4.7) are divisible by 0.4, so a greedy algorythm may work just fine.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://453766]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2024-04-19 04:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found