Haskell Knapsack

Question

J'ai écrit une réponse au problème de l'un havresac borné de chaque élément Scala, et avons essayé la transposition à Haskell avec le résultat suivant:

knapsack :: [ (Int, Int) ] -> [ (Int, Int) ] -> Int -> [ (Int, Int) ] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [ ] [ knapsack (y : xs) (filter (y /=) ys) max | y <- ys 
     , weightOf(y : xs) <= max ] 

maxOf :: [ (Int, Int) ] -> [ (Int, Int) ] -> [ (Int, Int) ] 
maxOf a b = if valueOf a > valueOf b then a else b 

valueOf :: [ (Int, Int) ] -> Int 
valueOf [ ]  = 0 
valueOf (x : xs) = fst x + valueOf xs 

weightOf :: [ (Int, Int) ] -> Int 
weightOf [ ]  = 0 
weightOf (x : xs) = snd x + weightOf xs 

Je ne cherche pas pour obtenir des conseils sur comment nettoyer le code, juste pour le faire fonctionner. A ma connaissance, il devrait faire ce qui suit:

• Pour chaque option tuple (en ys)
  • si le poids du tuple courant (y) et le total de fonctionnement (xs) combinée est inférieure à la capacité
  • obtenir le havresac optimal qui contient le tuple courant et le total actuel (xs), en utilisant les tuples disponibles (en ys) moins le tuple
• Enfin, obtenir le plus précieux de ces résultats et rendement

* Editer: * Désolé, j'ai oublié de dire ce qui ne va pas ... Donc ça compile bien, mais ça donne la mauvaise réponse. Pour les entrées suivantes, ce que je pense et ce qu'elle produit:

knapsack [] [(1,1),(2,2)] 5 
Expect: [(1,1),(2,2)] 
Produces: [(1,1),(2,2)] 

knapsack [] [(1,1),(2,2),(3,3)] 5 
Expect: [(2,2),(3,3)] 
Produces: [] 

knapsack [] [(2,1),(3,2),(4,3),(6,4)] 5 
Expect: [(2,1),(6,4)] 
Produces: [] 

Je me demandais ce qui pourrait être la cause de l'écart?

La solution, grâce à sepp2k:

ks = knapsack [] 

knapsack :: [ (Int, Int) ] -> [ (Int, Int) ] -> Int -> [ (Int, Int) ] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [ ] (xs : [ knapsack (y : xs) (ys #- y) max 
          | y <- ys, weightOf(y : xs) <= max ]) 

(#-) :: [ (Int, Int) ] -> (Int, Int) -> [ (Int, Int) ] 
[ ]  #- _ = [ ] 
(x : xs) #- y = if x == y then xs else x : (xs #- y) 

maxOf :: [ (Int, Int) ] -> [ (Int, Int) ] -> [ (Int, Int) ] 
maxOf a b = if valueOf a > valueOf b then a else b 

valueOf :: [ (Int, Int) ] -> Int 
valueOf [ ]  = 0 
valueOf (x : xs) = fst x + valueOf xs 

weightOf :: [ (Int, Int) ] -> Int 
weightOf [ ]  = 0 
weightOf (x : xs) = snd x + weightOf xs 

qui renvoie les résultats attendus, ci-dessus.

Answer 1

Vos premiers feux de cas quand ys contient. donc pour knapsack [foo,bar] [] 42, vous obtenez [foo, bar], ce qui est ce que vous voulez. Cependant, il ne se déclenche pas lorsque ys ne contient rien d'autre que des éléments qui vous placeraient au-dessus du poids maximum, c'est-à-dire que knapsack [(x, 20), (y,20)] [(bla, 5)] renverra [] et donc annulera le résultat précédent. Comme ce n'est pas ce que vous voulez, vous devez ajuster vos cas de sorte que le second cas se déclenche seulement s'il y a au moins un élément dans ys qui est inférieur au poids maximum.

Une façon de le faire serait de jeter tous les éléments que vous mettez sur le poids max quand récursion, de sorte que ce scénario ne peut tout simplement pas se produire.

Une autre façon serait de changer l'ordre des cas et d'ajouter un garde au premier cas qui dit que ys doit contenir au moins un élément qui ne vous met pas sur le poids total (et ajuster l'autre cas à ne pas exiger que ys soit vide).

PS: un autre problème sans rapport avec votre code est qu'il ne tient pas compte des doublons. C'est à dire. si vous l'utilisez sur la liste [(2,2), (2,2)] il agit comme si la liste était [(2,2)] parce filter (y /=) ys rejettera toutes les occurrences de y, pas seulement un.

Answer 2

Quelques améliorations sur votre version de travail:

import Data.List 
import Data.Function(on) 

ks = knapsack [] 

knapsack :: [(Int, Int)] -> [(Int, Int)] -> Int -> [(Int, Int)] 
knapsack xs [] _ = xs 
knapsack xs ys max = 
    foldr (maxOf) [] (xs: [knapsack (y:xs) (delete y ys) max 
          | y <- ys, weightOf(y:xs) <= max ]) where 
          weightOf = sum . map snd 

maxOf :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] 
maxOf a b = maximumBy (compare `on` valueOf) [a,b] where 
      valueOf = sum . map fst 

Answer 3

Puis-je suggère d'utiliser une approche de programmation dynamique?Cette façon de résoudre les problèmes de sac à dos 0-1 est presque péniblement lente, au moins quand la quantité de variables devient plus grande qu'environ 20. Alors que c'est simple, c'est trop inefficace. Voici mon coup à ce:

import Array 

-- creates the dynamic programming table as an array 
dynProgTable (var,cap) = a where 
    a = array ((0,0),(length var,cap)) [ ((i,j), best i j) 
         | i <- [0..length var] , j <- [0..cap] ] where 
     best 0 _ = 0 
     best _ 0 = 0 
     best i j 
      | snd (var !! (i-1)) > j = a!decline 
      | otherwise   = maximum [a!decline,value+a!accept] 
       where decline = (i-1,j) 
         accept = (i-1,j - snd (var !! (i-1))) 
         value = fst (var !! (i-1)) 

--Backtracks the solution from the dynamic programming table 
--Output on the form [Int] where i'th element equals 1 if 
--i'th variable was accepted, 0 otherwise. 
solve (var,cap) = 
    let j = cap 
     i = length var 
     table = dynProgTable (var,cap) 
     step _ 0 _ = [] 
     step a k 0 = step table (k-1) 0 ++ [0] 
     step a k l 
      | a!(k,l) == a!(k-1,l) = step a (k-1) l ++ [0] 
      | otherwise   = step a (k-1) (l - snd (var !! (k-1))) ++ [1] 
    in step table i j 

Dans l'entrée (var, cap), var est une liste de variables sous forme de 2-tuples (c, p), où c est le coût et w est la poids. cap est l'allocation de poids maximum. Je suis sûr que le code ci-dessus pourrait être nettoyé pour le rendre plus lisible et évident, mais voilà comment cela s'est avéré pour moi :) Où l'extrait de code par Landei ci-dessus est court, mon ordinateur a pris de nombreuses instances de calcul avec seulement 20 variables. L'approche de programmation dynamique ci-dessus m'a donné une solution pour 1000 variables plus rapidement.

Si vous ne connaissez pas la programmation dynamique, vous devriez consulter ce lien: Lecture slides on dynamic programming, cela m'a beaucoup aidé. Pour une introduction aux baies, consultez Array tutorial.