NOTE: **use Perl;** is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

gav

(email not shown publicly)

http://www.estey.com/

**AOL IM:** flufflegavin (**Add Buddy, Send Message**)

Hacker in NYC.

(email not shown publicly)

http://www.estey.com/

Hacker in NYC.

Sunday September 07, 2003

02:43 PM

This is my first attempt to solve the little problem I mentioned before. I have decided to call this the boxing golf balls problem*.

You are a company that sells golf balls which you sell in fixed box sizes, and given a fixed amount of inventory you want to find the most balls you can sell to use up the remainding balls i.e. you can't sell two balls as the smallest box you have is for three.

The MAX_PERMS is there because the amount of combinations for sets > 3 is huge and we seem to get close enough to the right answer quickly.

#!/usr/bin/perl -w

use strict;

use Test::More qw( no_plan );

use List::Permutor;

use constant MAX_PERMS => 1_000;

is(largest_sum(13, [3, 5, 7]), 13);

is(largest_sum(7, [4, 6, 12]), 6);

is(largest_sum(14, [3, 5, 9]), 14);

is(largest_sum(15, [3, 10, 25]), 15);

is(largest_sum(143, [3, 10, 25, 50, 100]), 143);

sub largest_sum {

my ($target, $set) = @_;

my @set = ();

foreach my $n (@$set) {

return $n if $target == $n;

return $target if ($target / $n) == int($target / $n);

if ($n < $target) {

my $num_of = 1;

while ($num_of * $n < $target) {

push @set, $n;

$num_of++;

}

}

}

my $perm = List::Permutor->new(@set);

my $highest = 0;

my $perms = 0;

while ($perms++ < MAX_PERMS and my @set = $perm->next) {

my $total = 0;

foreach my $n (@set) {

$total += $n;

if ($total == $target) {

return $target;

} elsif ($total > $target) {

$total -= $n;

$highest = $total if $total > $highest;

}

}

}

return $highest;

}

* This is actually a real-world problem for a client, I've just changed their business around because what they are doing makes no sense

Full

Abbreviated

Hidden

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.

## Can't tell (Score:2)

I'd attack it with a recursive routine that recurses for each possible component (ordered from largest down to smallest). For each one try as many as possible, down to zero, for each recursive attempt. I'd also keep track of the solution (with a hash of component->count pairs), since returning the way of achieving the maximum seems as important as finding the maximum possible. Short circuit the return if the exact target is ac