Stories
Slash Boxes
Comments
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

use Perl Log In

Log In

[ Create a new account ]

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.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • I didn't spend enough time to fully understand your code, but it feels off.

    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