Ganz simpel nach dem Algorithmus, der auf der deutschen Wikipedia unter Rucksackproblem aufgeführt wurde.
Dazu Python und NumPy genutzt.

Code python:

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

# -*- encoding: utf8 -*-   import sys import numpy   # Diese Klasse beschreibt eine Süßigkeit # class Candy( object ):     def __init__( self, name, weight, energy ):         self.name = name         self.weight = weight         self.energy = energy         def __str__( self ):         return self.name         __repr__ = __str__   # Rucksackproblem mittels dynamischer Programmierung lösen. # Siehe dazu: [url]http://de.wikipedia.org/wiki/Rucksackproblem#L.C3.B6sung_mittels_dynamischer_Programmierung[/url] # def choose( candies, threshold ):     n = len(candies)     r = numpy.zeros( (n + 1, threshold + 1), dtype = int )     p = numpy.zeros( (n + 1, threshold + 1), dtype = tuple )         minj = min( c.weight for c in candies )         for i in reversed(range(n)):         for j in xrange(minj, threshold+1):             if candies[i].weight <= j:                 c1 = candies[i].energy + r[i+1,j-candies[i].weight]                 c2 = r[i+1, j]                 if c1 > c2:                     r[i,j] = c1                     p[i,j] = (i+1, j - candies[i].weight)                 else:                     r[i,j] = c2                     p[i,j] = p[i+1,j]                                 else:                 r[i,j] = r[i+1,j]                 p[i,j] = p[i+1,j]         # Jetzt den Pfad durch die Matrix berechnen     path = []     x = p[(0, threshold)]     while x:         path.append( candies[x[0]-1] )         x = p[x]         return path     def main():     readline = lambda: sys.stdin.readline().strip()         # Maximales Gewicht einlesen     threshold = int( readline() )     candies = []         # Süßigkeiten einlesen     name = readline()     while name:         weight, energy = map( int, readline().split() )         candies.append( Candy( name, weight, energy ) )         name = readline()         # Rucksack klug füllen     knapsack = choose( candies, threshold )         # Und Infos ausgeben     print "Optimale Auswahl:", ", ".join( map( str, knapsack ) )     print "Masse:", sum( c.weight for c in knapsack ), "g"     print "Nährwert:", sum( c.energy for c in knapsack ), "kcal"     if __name__ == '__main__':     main()