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

## All the Perl that's Practical to Extract and Report

#### gav (2710)

gav
(email not shown publicly)
http://www.estey.com/
AOL IM: flufflegavin (Add Buddy, Send Message)

Hacker in NYC.

### Journal of gav (2710)

Sunday September 07, 2003
02:43 PM

### solving the set problem

[ #14565 ]

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 :)

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.