Meine Überlgung ist recht simpel.

1) Beerechne pro Süssigkeit das Verhältnis von Gewicht und Kcal.
2) Versuche die Süssigkeiten mit dem meisten Kcal pro Gramm in den Korb zu tun. Hat diese keinen Platz, versuch es mit der nächsten

Ebenfalls habe ich die Ausgangslage so angepasst, dass die Anzahl der Süssigkeiten mitgegeben werden kann.

Code :
1
2
3
4
5
6

500
Nougat-Eier
84 427
Fondant-Eier
2 150 540
...
Dies bedeutet: 1 Nougat-Ei, 2 Fondant-Eier

Da ich grad Spass an PHP hab, habe ich auch diese Fingerübung in PHP umgesetzt.

Code PHP:
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

<?php
//Süssigkeitengenerator
//$lines entspricht nachher dem gleichen Muster wie die Datei mit file() ausgelesen
$lines[] = 500;
for ($i = 0; $i<10000; $i++){
    $c = mt_rand(1, 5);
    $g = mt_rand(5, 500);
    $k = mt_rand(5, 1000);
    $s = '';
    for($j = 0; $j < mt_rand(6, 10); $j++){
        $s .= chr(mt_rand(65, 90));
    }
    $lines[] = "$c $g $k";
    $lines[] = $s;
}
 
 
 
/**
 * @copyright   mpl by ERB software
 * @project     [url]http://www.tutorials.de[/url] Coder Quiz15
 * @version     1.0 / 6.04.2010
 * @author      [email]stefan.erb@erb-software.com[/email]
 */
define('C_ZAHLEN_PATTERN', '/^(?:([[:digit:]]+)[ ]+|)([[:digit:]]+)[ ]+([[:digit:]]+)$/');
 
/**
 * Klasse für die Süssigkeiten.
 */
class Sweety{
    public function __construct($name, $zahlen){
        $this->name = $name;
        $this->gramm = (Integer)$zahlen[0];
        $this->kcal = (Integer)$zahlen[1];
        $this->kcalPerGramm = $this->kcal/$this->gramm;
    }
}
 
/**
 * Gibt einen Array mit dem Inhalt eines Properties einer Klasse in einem Array zurück
 */
function getProps(&$array, $property){
    return array_map(create_function('$sweety', "return \$sweety->{$property};"), $array);
}
 
/**
 * Programm start
 */
$starttime = microtime(true);
//Alle Zeilen auslesen
$lines = array_filter(array_map('trim', file('input.txt')));
 
//Erste Zeile beinhaltet das maximale Traggewicht
$max = trim(array_shift($lines));
 
//Array initialisieren
$sweeties = array();
//Aus den Zielen der Input-Datei ein Array mit Süssigkeiten erstellen
foreach($lines as $line){
    if(preg_match(C_ZAHLEN_PATTERN, trim($line), $match)){
        //Gefundener String entfernen
        array_shift($match);
        //Anzahl Süssigkeiten dieses Types ermitteln
        $count = ($count = array_shift($match)) ? $count : 1;
        //Anzahl Süssigkeiten des Types zur Süssigkeitenliste hinzufügen 
        $sweeties += array_fill(count($sweeties), $count, new Sweety($name, $match));
    }elseif(trim($line)){
        $name = trim($line);
    }    
}
 
//Ein Index mit der Gewichtung erstellen
$gewichtung = getProps($sweeties,'kcalPerGramm');
 
//Nach kcal pro gramm absteigend sortieren so dass die Süssigkeiten mit dem meisten kcal pro gramm zuerst kommen
arsort($gewichtung);
 
//Nach kcal pro Gramm durchgehen und schauen ob die Süssigkeit noch Platz im Korb hat.
foreach(array_keys($gewichtung) as $index){
    $sweety = $sweeties[$index];
    if($max >= ($gewicht + $sweety->gramm)){
        $gewicht += $sweety->gramm;
        //Liste mit den selektierten Süssigkeiten
        $selected[] = $sweety;
    }
}
 
//Namen zählen und den String entsprechend zurückgeben
//Falls mit dem Zufallsgeneratr per zufall identische Namen generiert werden, 
//führt hier array_count_values() zu einem Fehler
foreach(array_count_values(getProps($selected, 'name')) as $name => $count){
    $strings[] = (($count > 1) ? "{$count} x " : "") ."'{$name}'";
}
 
//Ausgabe
echo implode(', ', $strings)."<br />\n";
echo "Gewicht: ".array_sum(getProps($selected, 'gramm'))."<br />\n";
echo "kCal:    ".array_sum(getProps($selected, 'kcal'))."<br />\n";
echo microtime(true) - $starttime ." Sekunden";
 
?>