use Perl

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