50 Zeilen BruteForce: Beim Schreiben und in der Ausführung..

Das Skript probiert einfach alle möglichen Kombinationen aus - 2 "hoch" der-Anzahl-der-Sweeties-die-nicht-schon-allein-über-das-Maximum-hinaus-schießen ergibt die Anzahl der möglichen Kombinationen - diese werden in einer Schleife abgezählt. In jeder Iteration repräsentiert das Bitmuster der Zahl die aktuelle Kombi zum Testen, ein wenig Shiften und schon kann man mit den Werten arbeiten:

Code Perl:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#!/usr/bin/perl -w use strict;   sub usage {     print STDERR <<'EOT;'; Na, da stimmt wohl was mit der Eingabe nicht! Schau mal hier: tutorials.de/forum/diskussion/357969-quiz-15-lisas-osternest.html EOT;     exit -1; }   my($max, @sweeties, %best, $i, $j, $k) = ();   # Input $max = int <STDIN> or &usage; while(1) {     my $name = <STDIN>;     last unless $name;     chomp $name;     last if $name =~ /^\s*$/ and @sweeties;     &usage unless $name =~ s/^\s*(.+?)\s*$/$1/;     my $data = <STDIN>;     &usage unless $data =~ /^\s*([0-9]+)\s+([0-9]+)\s$/;     next if $1 > $max;     push @sweeties, { name => $name, g => $1, kcal => $2 }; } &usage unless @sweeties;   # Process %best = (%{ $sweeties[0] }, no => 1 ); CANDIDATE: for($i = 2; $i != 2 ** @sweeties; ++$i) {     my($g, $kcal) = (0, 0);     for(($j, $k) = ($i, 0); 0 != $j; $j >>= 1, ++$k) {         next unless $j & 1;         next CANDIDATE if ($g + $sweeties[$k]{g}) > $max;         $g += $sweeties[$k]{g};         $kcal += $sweeties[$k]{kcal};     }     %best = ( no => $i, g => $g, kcal => $kcal )         if $kcal > $best{kcal} or ($kcal == $best{kcal} and $g < $best{g}); }   # Output print "Optimale Auswahl: "; for(($j, $k) = ($best{no}, 0); 0 != $j; $j >>= 1, ++$k) {     print $sweeties[$k]{name}, 1 == $j? "\n": ", " if $j & 1; } print "Masse: ", $best{g}, " g\n",       "Nährwert: ", $best{kcal}, " kcal\n";

Mal schauen ob ich noch Zeit und Muße finde, mir schwirren da schon ein paar Optimierungen durch den Kopf...
Bis dahin -

Gruß
Enum

Soo, nachdem ich durch die in der Diskussion genannten Zeiten angespornt wurde hab' ich die angekündigten Optimierungen vorgenommen - eigentlich hab' ich nicht viel von der alten Version übrig gelassen...
Anstelle jede mögliche Kombination abzuarbeiten, nutze ich jetzt die Ergebnisse vorheriger Berechnungen. Ob das nun generische Programmierung ist oder nicht weiß ich nicht, aber es funktioniert und ist halbwegs performant:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

lenny:~/oster-quiz$ time ./lisa.pl < 100leckereien.txt; echo Optimale Auswahl: Vollmilch-Eierlikör-Schokohase, Joghurt-Trüffel-Krokant-Goldhase, Trüffel-Butter-Eierlikör-Ostereier Gewicht: 494 Nährwert: 3393 kcal   real    0m42.242s user    0m39.786s sys     0m0.660s   lenny:~/oster-quiz$ time ./lisa.pl < 50leckereien.txt; echo Optimale Auswahl: Waffel-Joghurthase, Marzipan-Vollmilch-Goldeier, Vollmilch-Krokant-Waffelhase Gewicht: 494 Nährwert: 3392 kcal   real    0m2.379s user    0m2.332s sys     0m0.036s   lenny:~/oster-quiz$

Hier die überarbeitete Version in Perl:

Code Perl:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#!/usr/bin/perl -w no warnings "recursion"; use strict;   my($MAX, @BEST, @SWEETIES, @RESULT) = (     (int <STDIN> or &usage), { n => ["dummy"], g => 0, c => 0, x => 0 } );   sub usage {     print STDERR <<'EOT;'; Na, da stimmt wohl was mit der Eingabe nicht! Schau mal hier: tutorials.de/forum/diskussion/357969-quiz-15-lisas-osternest.html EOT;     exit -1; }   sub candidate {     if($BEST[0]{c} < $_[0]{c}) {         @BEST = @_;     } elsif($BEST[0]{c} == $_[0]{c}) { #       if($BEST[0]{g} > $_[0]{g}) { #           @BEST = @_; #       } elsif($BEST[0]{g} == $_[0]{g}) {             push @BEST, @_; #       }     } }   sub calculate {     my($first, @result, $g, @combis) = ();     if($first = shift(@_)) {         for(@combis = calculate(@_)) {             if(($g = $_->{g} + $first->{g}) <= $MAX) {                 push @result,                      {                          x => [ @{$first->{x}}, @{$_->{x}} ],                          g => $g,                          c => $first->{c} + $_->{c}                      };             }         }         push @result, $first, @combis;     }     return @result; }   while(<>) {     s/\s*$//; # chomp is nich weil CR/LF. blöd.     <> =~ /^([0-9]+)\s+([0-9]+)/;     next if $1 > $MAX;     push @SWEETIES,     {         n => $_,         g => $1,         c => $2,         x => [scalar @SWEETIES]     }; } usage unless 1 < @SWEETIES; for(calculate(@SWEETIES)) {     candidate $_; } print "Optimale Auswahl: ", $SWEETIES[shift @{$BEST[0]{x}}]{n}; while($_ = shift @{$BEST[0]{x}}) {     print ", ", $SWEETIES[$_]{n}; } print "\nGewicht: ", $BEST[0]{g}, "\nNährwert: ", $BEST[0]{c}, " kcal\n";   __END__

Da mich die Zeiten von OnlyFoo allerdings sehr beeindruckt hatten, hab' ich den Code noch in C übersetzt...

Gruß
Enum