Haskell ранец

Question

Я написал ответ на ограниченную задачу о рюкзаке с одним из каждого пункта в Scala, и попытался перенося его на Haskell со следующим результатом:

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 

Я не ищу советы о как очистить код, просто чтобы он работал. Насколько мне известно, он должен делать следующее:

• Для каждого варианта кортежа (в ув)
  • если вес текущего кортежа (у) и нарастающим итогом (хв) в сочетании меньше, чем емкость
  • получить оптимальный ранец, который содержит текущий кортеж и текущую сумму (Xs), используя доступные наборы (в увах) меньше текущего кортеж
• и наконец, получить наиболее ценные из этих результатов и возврата его

* Редактировать: * Извините, забыли сказать, что не так ... Так что это скомпрометировано, но это дает неправильный ответ. Для следующих входов, что я ожидаю и что она производит:

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

Так мне было интересно, что может быть причиной расхождения?

Раствор, благодаря 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 

который возвращает ожидаемые результаты, выше.

Answer 1

Ваш первый случай срабатывает, когда ys содержит. поэтому для knapsack [foo,bar] [] 42 вы возвращаетесь [foo, bar], что и есть то, что вы хотите. Однако он не срабатывает, когда ys не содержит ничего, кроме элементов, которые могли бы поставить вас на максимальный вес, то есть knapsack [(x, 20), (y,20)] [(bla, 5)] вернет [] и таким образом отбросит предыдущий результат. Поскольку это не то, что вы хотите, вы должны скорректировать свои случаи, чтобы второй случай срабатывал только в том случае, если есть хотя бы один элемент в ys, который ниже максимального веса.

Один из способов сделать это - выкинуть любые элементы, которые поместили бы вас на максимальный вес при рекурсии, чтобы этот сценарий просто не мог произойти.

Другим способом было бы переключить порядок корпусов и добавить защитник в первый случай, который гласит, что ys должен содержать хотя бы один элемент, который не помещает вас в общий вес (и отрегулировать другой случай, чтобы не было требуется ys быть пустым).

PS: Другая, не связанная с вашим кодом проблема заключается в том, что она игнорирует дубликаты. То есть если вы используете его в списке [(2,2), (2,2)], он будет действовать так, как если бы список был только [(2,2)], потому что filter (y /=) ys выкинет все вхождения y, а не только один.

Answer 2

Некоторые улучшения в вашей рабочей версии:

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

Я мог бы предложить использовать динамический подход программирования?Этот способ решения проблем с рюкзаком 0-1 почти болезненно медленный, по крайней мере, когда количество переменных становится больше, чем около 20. Хотя это просто, это слишком малоэффективно. Вот мой выстрел на него:

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 

В вход (вар, крышки), вар список переменных в виде 2-кортежей (с, ш), где с является стоимость и вес является вес. колпачок - максимальный вес.

Я уверен, что код выше можно было бы очистить, чтобы сделать его более читабельным и очевидным, но вот как это получилось для меня :) Там, где фрагмент кода от Landei выше короткий, мой компьютер занимал возрастные вычислительные экземпляры только с 20 переменных. Подход с динамическим программированием выше дал мне решение для 1000 переменных быстрее.

Если вы не знаете о динамическом программировании, вы должны проверить эту ссылку: Lecture slides on dynamic programming, это очень помогло мне.

Для ознакомления с массивами ознакомьтесь с Array tutorial.