# Global variables
my @files;                    # Array of (Size,Name)
my $nr_entries = 0;           # Anzahl gefundener Dateien
my @opt_solution_sizes;       # sizes of current opt. combination 
my @opt_solution_idx;         # indices of current opt. combination 
my $opt_solution_tot;         # size of current opt. combination 

# Read files and sort biggest first
open F, "<$filename" 
    or die "Cannot open $filename\n$!";
while (my $line = <F>)
{
    chomp $line;
    my ($size, $name) = split /\s+/, $line, 2;
    push @files, [$size, $name];
    $nr_entries++;
}
close F;
@files = sort {$$b[0] <=> $$a[0]} @files;


sub TrySolution
{
    my $stufe          = shift;
    my @solution_sizes = @{ $_[0] };
    my @solution_idx   = @{ $_[1] };
    my $solution_tot   = sum(@solution_sizes);

    if ( $solution_tot > $opt_solution_tot )
    {
        # new Optimum
        @opt_solution_sizes = @solution_sizes;
        @opt_solution_idx   = @solution_idx;
        $opt_solution_tot   = sum(@opt_solution_sizes);
    }

    if ($stufe==$nr_entries)
    {   # last entry
        return;
    }

    # retry, for all entries, that can give possible solutions
    for my $try ( $stufe..($nr_entries-1) )
    {   
        my $try_size = $files[$try]->[0];
        if ( $solution_tot+$try_size < $options{cdsize})
        {
            # If possible, then try with extended set
            TrySolution ( $try+1, 
                	  [@solution_sizes, $try_size], 
                	  [@solution_idx, $try] );
        }
    }
}


# Main
while (@files)
{
    my @new_set = ();
    @opt_solution_sizes = ();
    @opt_solution_idx   = ();
    $opt_solution_tot  = 0;

    TrySolution (0, [], [] );
    print "Optimal solution is $opt_solution_tot with ", 
           commify_series (@opt_solution_sizes), "\n"; 
    # see Perl Cookbook for commify_series, nice string out of list

    @new_set = ();
    foreach my $idx ( reverse @opt_solution_idx)
    {   # start from end, if array is cut in the middle
        unshift @new_set, splice @files, $idx, 1;
        $nr_entries--;     # global counter, left input list entries
    }
    # Now output result
    print "\nNext Set is:\n", '-' x 10, "\n";
    for (my $i=0; $i < @new_set; $i++) 
    { 
        printf "%2d) [%3d] %s\n", 
               $i, $new_set[$i]->[0], $new_set[$i]->[1]; 
    }
    print "\n";
}