2

これが分数ナップサック問題を解くための私のコードです。ナップへの入力は次の形式である必要があります

[("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 []

他に何ができるかよくわかりません。私がここに座って壁に頭を1時間叩く前に、誰かが明らかな間違いを指摘する可能性がありますか？

4

2 に答える 2

2

4 タプル inknap2と 3 タプル inがどのように適合するかはわかりませんが、パターン マッチして, ,などknapをドロップすると、問題がより明確になります。headtailthrd4thirteenth17

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 のケースでパターン マッチを行い、他のケースと区別することができます。

于 2012-07-30T21:37:55.743 に答える
0

編集、めちゃくちゃ、やり直し：

yで使用されている引数にエラーがあることがわかりますknap2 x y []。トリプル (実際のタイプ) ですが、4 倍になることをknap2 期待しています。

于 2012-07-30T20:45:05.820 に答える