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 :)
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 achived, to bypass the n**2 number of cases. Another short circuit would be to keep track of each total that had been seen and the number of remaining components that were available to be applied - if the same total is later seen, it can be skipped if there are the same or fewer components left. (I.e. with [9,7,4,3] we see 16 as [9,7] and analyse all ways of adding 4 and/or 3 to it; so when we later see 16 as [4,4,4,4] and only have the option of adding 3's to it, there is no need to investigate. On the alternative, with [9,6,5,3,2] we will see 12 as [9,3] with the possibility of adding 2's; then later see 12 as [6,6] with the possibility of adding 5's, 3's, or 2's - there may be alternatives there that have not yet been examined.)