Haskell mochila

Question

he escrito una respuesta al problema de la mochila acotada con uno de cada elemento de Scala, y trató de transponer a Haskell con el siguiente resultado:

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 

No estoy en busca de consejos sobre cómo limpiar el código, solo para que funcione. Que yo sepa, que debería estar haciendo lo siguiente:

• Para cada opción tupla (en ys)
  • si el peso de la tupla actual (y) y el total de ejecución (x) combinado es menor que el capacidad
  • conseguir la mochila óptima que contiene la tupla actual y el total actual (xs), utilizando las tuplas disponibles (en ys) menos la tupla actual
• Por último, conseguir el más valioso de estos resultados y de retorno es

* Editar: * Lo siento, se olvidó de decir lo que está mal ... Así que compila bien, pero da la respuesta incorrecta. Para las siguientes entradas, lo que espero y lo que produce:

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: [] 

así que me preguntaba lo que podría ser la causa de la discrepancia?

La solución, gracias a 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 

que devuelve los resultados esperados, arriba.

Answer 1

Su primer caso se activa cuando contiene ys. entonces para knapsack [foo,bar] [] 42, obtiene [foo, bar], que es lo que quiere. Sin embargo, no se activa cuando ys no contiene nada, excepto elementos que le pondrían por encima del peso máximo, es decir, knapsack [(x, 20), (y,20)] [(bla, 5)] devolverá [] y descartará el resultado anterior. Como esto no es lo que desea, debe ajustar sus casos para que el segundo caso solo se dispare si hay al menos un elemento en ys que está por debajo del peso máximo.

Una forma de hacerlo sería tirar cualquier elemento que lo coloque sobre el peso máximo al repetir, para que ese escenario simplemente no pueda suceder.

Otra forma sería cambiar el orden de las cajas y agregar un protector al primer caso que dice que ys debe contener al menos un elemento que no lo coloque sobre el peso total (y ajuste el otro caso a no requiere ys para estar vacío).

PD: Otro problema no relacionado con su código es que ignora los duplicados. Es decir. si lo usa en la lista [(2,2), (2,2)], actuará como si la lista fuera [(2,2)] porque filter (y /=) ys arrojará todas las ocurrencias de y, no solo una.

Answer 2

Algunas mejoras en su versión de trabajo:

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

¿Puedo sugerir el uso de un enfoque de programación dinámica?Esta forma de resolver los problemas de la mochila 0-1 es casi dolorosamente lenta, al menos cuando la cantidad de variables es mayor que alrededor de 20. Si bien es simple, es demasiado ineficaz. Aquí está mi tiro en él:

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 

En la entrada (var, cap), var es una lista de variables en la forma de 2-tuplas (c, w), donde c es el costo y w es la peso. el límite es la asignación de peso máxima.

Estoy seguro de que el código anterior podría limpiarse para hacerlo más legible y obvio, pero así fue como me resultó :) Donde el fragmento de código de Landei es corto, mi computadora tardó años en computar instancias con solo 20 variables. El enfoque de programación dinámica anterior me dio una solución para 1000 variables más rápido.

Si no sabe acerca de la programación dinámica, debe consultar este enlace: Lecture slides on dynamic programming, me ayudó mucho.

Para una introducción a las matrices, visita Array tutorial.