A further solution to "Dropbox Diet" from http://www.dropbox.com/jobs/challenges This one performs much better with larger inputs by processing smaller combinations before larger.

dropbox-diet.pl

#!/usr/bin/env perl

use strict;
use warnings;

my %exercise = ();
my %food = ();
my $lines = 0;

# read food and exercise options into separate lists based on positive or negative calories
foreach my $line (<>) {
    if ($line =~ m/^(\d+)$/) {
        $lines = $1;
    }
    
    if (0 == $lines) { last; }
    
    if ($line =~ m/^([^ ]+) *(-?\d+)$/) {
        if ($2 > 0) {
            $food{$1} = $2;
            
        } elsif ($2 < 0) {
            $exercise{$1} = $2;
            
        }
        
        $lines --;
    }
}

my @food     = (keys %food);
my @exercise = (keys %exercise);

my %seen = ();  # hash to track processed combinations

# iterating using max, min, and $current_max allows processing smaller combinations before bigger
# as in:
#   1,1 1,2 2,1 2,2 1,3 2,3 3,1 3,2 3,3
# rather than: 
#   1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,2

for my $current_max (1..max($#food+1,$#exercise+1)) {

    for my $food_size (1..min($current_max,$#food+1)) {
        for my $exercise_size (1..min($current_max,$#exercise+1)) {
            if (defined $seen{"$food_size,$exercise_size"}) {
                next;
            }
            $seen{"$food_size,$exercise_size"} ++;
            
            # calculate the combinations
            my $food_iter = combo($food_size, @food);
            my $exercise_iter = combo($exercise_size, @exercise);
            
            # cache the exercise combinations because they'll be needed repeatedly
            my @exercise_cache = ();
            while ( my @pick_exercise = $exercise_iter->() ) {
                push @exercise_cache, [@pick_exercise];
            }
            
            # iterate over the combinations
            while ( my @pick_food = $food_iter->() ) {
                foreach my $pick_exercise (@exercise_cache) {
                    my $total = 0;
                    map $total += $exercise{$_}, @$pick_exercise;
                    map $total += $food{$_}, @pick_food;
                    
                    # print the solution
                    if (0 == $total) {
                        foreach my $item (sort (@$pick_exercise, @pick_food)) { print "$item\n"; }
                        exit;
                    }
    
                }
            }
            
        }
    }

}

print "no solution\n";

sub max
{
    my ($a,$b) = (@_);
    return ($a>$b?$a:$b);
}
sub min
{
    my ($a,$b) = (@_);
    return ($a<$b?$a:$b);
}

# from http://www.perlmonks.org/?node_id=371228
sub combo {
    my $by = shift;
    return sub { () } if ! $by || $by =~ /\D/ || @_ < $by;
    my @list = @_;

    my @position = (0 .. $by - 2, $by - 2);
    my @stop     = @list - $by .. $#list;
    my $end_pos  = $#position;
    my $done     = undef;

    return sub {
        return () if $done;
        my $cur = $end_pos;
        {
            if ( ++$position[ $cur ] > $stop[ $cur ] ) {
                $position[ --$cur ]++;
                redo if $position[ $cur ] > $stop[ $cur ];
                my $new_pos = $position[ $cur ];
                @position[ $cur .. $end_pos ] = $new_pos .. $new_pos + $by;
            }
        }
        $done = 1 if $position[0] == $stop[0];
        return @list[ @position ];
    }
}