1 files changed, 12 insertions, 12 deletions

diff --git a/AufgabeFFP4.hs b/AufgabeFFP4.hs
index 758bee4..8e7cbf1 100644
--- a/AufgabeFFP4.hs
+++ b/AufgabeFFP4.hs
@@ -1,6 +1,8 @@
 module AufgabeFFP4
 where
 
+import List
+
 type Weight    = Int             -- Gewicht
 type Value     = Int             -- Wert
 type MaxWeight = Weight          -- Hoechstzulaessiges Rucksackgewicht
@@ -27,26 +29,17 @@ succKnp (v, w, limit, objects, psol) =
       v + v',
       w + w',
       limit,
-      filterOne (== (w', v')) objects,
+      filterOne (== (w', v')) objects2,
       (w', v') : psol
     )
   ) objects2
   where
     objects2 = filter (\(w', v') -> (w + w') <= limit) objects
 
--- TODO: delete?
-succKnp2 :: NodeKnp -> [(Value, Weight, MaxWeight, [Object], SolKnp)]
-succKnp2 (v, w, limit, objects, psol) =
-  [(v + v',
-    w + w',
-   limit,
-   [ (w'', v'') | (w'', v'') <- objects, (w'' >= w')],
-   (w', v') : psol)
-  | (w', v') <- objects, w + w' <= limit ]
-
 -------------------------------------------------------------------------------
 
 goalKnp :: NodeKnp -> Bool
+goalKnp (_, _, _, [], _) = True
 goalKnp (_, w, limit, ((w', _) : _), _) = (w + w') > limit
 
 -------------------------------------------------------------------------------
@@ -85,9 +78,16 @@ searchDfs succ goal x = search' (push x emptyStack)
 
 -------------------------------------------------------------------------------
 
+cmpObject :: Object -> Object -> Ordering
+cmpObject (w, v) (w', v')
+  | w == w' = compare v v'
+  | otherwise = compare w w'
+
+-- it's safe to use maximum here as it will look at the first value of each tuple only
 knapsack :: Objects -> MaxWeight -> (SolKnp, Value)
 knapsack objects limit = (psol, v)
-  where (v, _, _, _, psol) = maximum (searchDfs succKnp goalKnp (0, 0, limit, objects, []))
+  where
+    (v, _, _, _, psol) = maximum (searchDfs succKnp goalKnp (0, 0, limit, sortBy cmpObject objects, []))
 
 -------------------------------------------------------------------------------