Hi Chris, Just back from a week's leave - I was working on a similar problem before I left.
Here's my code: http://dev2.gardyneholt.co.nz/Mike's%20Test%20Code/changemaking.phps <http://dev2.gardyneholt.co.nz/Mike%27s%20Test%20Code/changemaking.phps> Or in action: http://dev2.gardyneholt.co.nz/Mike's%20Test%20Code/changemaking.php <http://dev2.gardyneholt.co.nz/Mike%27s%20Test%20Code/changemaking.phps> To use it, call bestPackSize(t, array of s-values) and it's return an array of the values from /s/ that it used to sum to the value of t. It assume an infinite number of of each value is /s/ are available. - Mike On 10/12/2008 22:31, Chris Burgess wrote: > I'd be interested in PHP-specific solutions, or general reading, on this > "knapsack-like" problem. > > I have a series of numeric values /s/, and a few values /t/ which need > to be matched against entries from /s/. > > The values in /t/ are sums of one or several values from /s/. > > How to quickly identify the combinations of /s/-values which potentially > result in a given /t/ sum? > > > > -- Mike Cochrane Web Team Leader gardyneHOLT - design partners 18 Beresford Square Newton PO Box 3340 Auckland New Zealand p +64 9 300 3155 f +64 9 302 3349 m 021 545 565 skype gardyneholt_mikec www.gardyneholt.co.nz DISCLAIMER: This electronic message, together with any attachments, was created solely for the use of the intended recipient(s), and may be confidential. Views expressed may be those of the individual sender and are not necessarily endorsed by gardyneHOLT. If you are not the intended recipient, please advise us by return e-mail that you have received the message in error and then delete it. Do not copy, disclose or use the contents in any way. --~--~---------~--~----~------------~-------~--~----~ NZ PHP Users Group: http://groups.google.com/group/nzphpug To post, send email to [email protected] To unsubscribe, send email to [email protected] -~----------~----~----~----~------~----~------~--~---
