eigene Datentypen in Haskell < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:13 Do 04.01.2007 | | Autor: | Oekel |
| Aufgabe | Das Problem stellt sich wie folgt dar: jedes Geschenk p hat einen Namen (irgendeine Bezeichnung),
eine Gr¨oße (Volumen) s(p), und ein Gewicht w(p). Jeder Sack hat das gleiche
Fassungsverm¨ogen S. Zu finden ist jetzt aus einer Menge P von Geschenken eine Teilmenge
{p1, . . . , pn} P, deren Gesamtvolumen kleiner oder gleich dem Volumen des Sackes ist
n Xi=1
s(pi) S
aber deren Gesamtgewicht optimal ist, d.h. alle anderen Mengen von Geschenken, die auch
in den Sack passen w¨urden, haben weniger (oder gleich viel) Gewicht.
In Haskell ausgedr¨uckt, modellieren Sie zuerst den Datentyp Present, der Geschenke repr
¨asentiert, sowie die Funktionen
data Present
name :: Present -> String
size :: Present -> Double
weight :: Present -> Double
Die eigentliche Packfunktion ist dann
pack :: [Present]-> Double-> [Present]
die aus einer Menge von Geschenken f¨ur ein gegebenes Sackvolumen die in Hinsicht auf
das Geschenkgewicht optimale Bepackung ausw¨ahlt. |
Habe das Problem selber gelöst!
Allerdings komme ich zu einem neuem Probem.
Hier erstmal meine Lösung:
type Name = String
type Size = Double
type Weight = Double
--Hier ist die Reihenfolge zu beachten, da 'deriving (Ord)'
--die Bewertung von links nach rechts vornimmt, womit wir uns ein
data Presents = Present Size Weight Name
deriving (Show,Eq,Ord)
testGeschenke :: [Presents]
testGeschenke = [(Present 1 30 "Trommel"),(Present 0.5 5 "Barbie"),(Present 0.2 10 "CD"),(Present 2 5 "Eimer"),
(Present 30 1000 "Auto"),(Present 35 10 "Risenballon"),(Present 15 2 "Lampe"),(Present 3 20 "TFT")]
name :: Presents -> String
name (Present _ _ name) = name
size :: Presents -> Double
size (Present size _ _) = size
weight :: Presents -> Double
weight (Present _ weight _) = weight
--------------------------------------------------------
---Sortieren von Listen durch einfuegen
sort :: Ord a => [a] -> [a]
sort xs = sorteinfuegenr xs []
sorteinfuegenr :: Ord a => [a] -> [a] -> [a]
sorteinfuegenr [] ys = ys
sorteinfuegenr (x:xs) [] = sorteinfuegenr xs [x]
sorteinfuegenr (x:xs) ys = sorteinfuegenr xs (sorteinfuegenr1 x ys)
sorteinfuegenr1 :: Ord a => a -> [a] -> [a]
sorteinfuegenr1 x [] = [x]
sorteinfuegenr1 x (y:ys) = if x <= y then x:y:ys
else y : (sorteinfuegenr1 x ys)
-- Insert-Sort: stabil und O(n) f"ur vorsortierte:
sorteinfuegeno xs = reverse (sorteinfuegenor xs [])
sorteinfuegenor :: Ord a => [a] -> [a] -> [a]
sorteinfuegenor [] ys = ys
sorteinfuegenor (x:xs) [] = sorteinfuegenor xs [x]
sorteinfuegenor (x:xs) ys = sorteinfuegenor xs (sorteinfuegenor1 x ys)
sorteinfuegenor1 :: Ord a => a -> [a] -> [a]
sorteinfuegenor1 x [] = [x]
sorteinfuegenor1 x (y:ys) = if x >= y then x:y:ys
else y : (sorteinfuegenor1 x ys)
--------------------------------------------------------
--Alle möglichen Kombinationen durch Listenkomprehension
pow :: [a] ->  a
pow [] = OOPS
pow (x:xs) = [ j ++ l | l <- pow xs, j <- ], [x ]
--Nur jene, die auch in den Sack passen...
[mm] findsum_s :: [/mm] [Presents] -> Double -> Presents
[mm] findsum_s [/mm] ls k = filter f (pow ls) where f ls = sum (map size ls) <= k
-- ...und die, die am schwersten ist
findsum_sheavy :: Presents ->[Presents]
findsum_sheavy ls = foldl1 maxweightls ls
--------------------------------------------------------
--Wir definieren ein neues max, um die Funktion foldl1 anwenden zu können
maxweight :: Presents -> Presents -> Presents
maxweight x y |(weight x) <= (weight y) = y
|otherwise = x
maxweightls :: [Presents] -> [Presents] -> [Presents]
maxweightls x y |(sum(map weight x)) <= (sum(map weight y)) = y
|otherwise = x
maxsize :: Presents -> Presents -> Presents
maxsize x y |(size x) <= (size y) = y
|otherwise = x
--------------------------------------------------------
pack:: [Presents] -> Double -> [Presents]
pack ls k= findsum_sheavy [mm] (findsum_s [/mm] (sort testGeschenke) k)
--hier steckt noch ein Fehler drin (Enlosschleife!!!)
packall :: [Presents] -> Double -> Presents
packall [] k = []
packall ls k = (pack ls k) : (packall (diff_ls (sort ls) (sort (pack ls k))) k)
--Differenz zweier SORTIERTER Listen bilden
diff_ls :: Ord a => [a] -> [a] -> [a]
diff_ls xs [] = xs
diff_ls [] ys = []
diff_ls (x:xs) (y:ys) = if x == y then diff_ls xs (y:ys)
else if x > y then diff_ls (x:xs) ys
else x: (diff_ls xs (y:ys))
Warum verfällt 'packall' in eine Endlosschleife?
Wie löse ich dieses Problem?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.infmath.de/thread.php?threadid=4974
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mo 08.01.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
