Hallo zusammen,

von mir gibt es noch schnell eine Lösung in Haskell, die dynamische Programmierung verwendet:
Code :
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

import Array
import Data.Char (isSpace)
import Data.List (break, intercalate)
import System.IO
import System.Environment (getArgs)
 
data Item = Item { getName :: String,
                   getWeight :: Int,
                   getValue :: Int
                 }
  deriving Show
 
parseInput :: Handle -> IO (Int, [Item])
parseInput h = do
  limitString <- hGetLine h
  let limit = read limitString
  items <- parseItems h
  return (limit, items)
 
parseItems :: Handle -> IO [Item]
parseItems h = do
  name <- hGetLine h
  if null name then
    return []
    else do
      weightValueString <- hGetLine h
      let (weightString, valueString) = break isSpace weightValueString
          (weight, value) = (read weightString, read valueString)
      rest <- parseItems h
      return ((Item name weight value) : rest)
 
solve :: Int -> [Item] -> [Item]
solve limit items =
  let indices = backtrack (n, limit)
  in map (\i -> items !! i) indices
  where n = length items
        weights = listArray (1, n) (map getWeight items)
        values  = listArray (1, n) (map getValue items)
        maxValue =
          listArray ((0, 0), (n, limit))
                    [calcMaxValue maxItem maxWeight | maxItem <- [0..n], maxWeight <- [0..limit]]
        calcMaxValue maxItem maxWeight
          | maxItem == 0 = 0
          | (weights ! maxItem) > maxWeight =
              maxValue ! (maxItem - 1, maxWeight)
          | otherwise =
              max (maxValue ! (maxItem - 1, maxWeight))
                  ((values ! maxItem) + (maxValue ! (maxItem - 1, maxWeight - (weights ! maxItem))))
        backtrack (0, _) = []
        backtrack (maxItem, maxWeight)
          | maxValue ! (maxItem, maxWeight) > maxValue ! (maxItem - 1, maxWeight) =
              (maxItem - 1) : backtrack (maxItem - 1, maxWeight - (weights ! maxItem))
          | otherwise = backtrack (maxItem - 1, maxWeight)
 
solutionToString :: [Item] -> String
solutionToString choice = 
  "Optimale Auswahl: " ++ intercalate ", " (map getName choice) ++ "\n" ++
  "Masse: " ++ show (sum (map getWeight choice)) ++ " g\n" ++
  "Nährwert: " ++ show (sum (map getValue choice)) ++ " kcal"
 
main :: IO ()
main = do
  args <- getArgs
  (limit, items) <-
    if null args then parseInput stdin
    else withFile (head args) ReadMode parseInput
  let choice = solve limit items
  putStrLn (solutionToString choice)
Die Hauptarbeit erledigt die Funktion solve, in der zunächst das 2D-Array maxValue aufgebaut wird. Es enthält an der Stelle (maxItem, maxWeight) die maximal erzielbare Menge an Kalorien, wenn man nur die ersten maxItem Leckereien verwendet und das Gesamtgewicht der Auswahl höchstens maxWeight sein darf. Die optimale Auswahl für das ursprüngliche Problem wind dann über Backtracking aus maxValue rekonstruiert.

Grüße,
Matthias