这是我解决分数背包问题的代码,knap 的输入应采用以下形式
[("label 1", value, weight), ("label 2", value, weight), ...]
输出应采用以下形式
[("label 1", value, solution_weight), ("label 2", value, solution_weight), ...]
代码:
import Data.List {- Need for the sortBy function -}
{- Input "how much can the knapsack hole <- x" "Possible items in sack [(label, value, weight), ...] <- y" -}
{-knap x [([Char], Integer, Integer), ... ] = -}
knap x [] = []
knap x y = if length y == 1
then
if x > last3 (head y)
then y
else [(frst3 (head y), scnd3 (head y), x)]
else
knap2 x y []
{- x is the knap max, y is the sorted frac list, z is the solution list -}
knap2 x y z = if x == 0
then z
else
if thrd4 (head y) > x
then [((frst4 (head y)), (scnd4 (head y)), x)]
else knap2 (x-(thrd4 (head y))) (tail y) (z++[((frst4 (head y)), (scnd4 (head y)), (thrd4 (head y)))])
{- take a list of labels, values, and weights and return list of labels and fractions -}
fraclist :: (Fractional t1) => [(t, t1, t1)] -> [(t, t1, t1, t1)]
fraclist xs = [(x, y, z, y/z) | (x, y, z) <- xs]
{- Sort the list -}
sortList x = sortBy comparator x
where comparator (_,_,_,d) (_,_,_,h) = if d > h then LT else GT
{- helper func to get values from tuples -}
frst3 (a,b,c) = a
scnd3 (a,b,c) = b
last3 (a,b,c) = c
frst4 (a,b,c,d) = a
scnd4 (a,b,c,d) = b
thrd4 (a,b,c,d) = c
last4 (a,b,c,d) = d
这是我收到的错误
Couldn't match expected type `(t1, t0, t2, t3)'
with actual type `(t1, t0, t2)'
Expected type: [(t1, t0, t2, t3)]
Actual type: [(t1, t0, t2)]
In the second argument of `knap2', namely `y'
In the expression: knap2 x y []
我不太确定我还能做什么。在我坐在这里用头撞墙一个小时之前,也许有人可以指出一个明显的错误(如果有的话)?
最佳答案
我无法判断 knap2
中的四元组和 knap
中的三元组应该如何组合在一起,但您会有更清晰的 View 如果您进行模式匹配并删除 head
、tail
、thrd4
、thirteenth17
等
knap _ [] = []
knap x [(a,b,c)] = if x > c then [(a,b,c)] else [(a, b, x)]
knap x abcs = knap2 x abcs []
knap2 0 abcs z = z
knap2 x abcs z = undefined -- not sure how to do this
-- but this makes sense, it seems:
knap3 0 _ zs = zs
knap3 _ [] _ = []
knap3 x ((a,b,c,d):abcds) zs =
if c > x then [(a, b, x)]
else knap3 (x - c) abcds (zs ++ [(a, b, c)])
或者类似的东西。您可以在单例情况下进行模式匹配,而不是编写 if length y == 1
; if x == 0
您可以对 0 的情况进行模式匹配,从而将其与其他情况区分开来,而不是使用相等性测试。
关于Haskell、Knapsack 未收到预期返回类型错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11729197/