0

我正在尝试用输入解决分数背包问题，

[("label 1", value, weight), ("label 2", value, weight), ...]

和输出，

[("label 1", value, solution_weight), ("label 2", value, solution_weight), ...]

但我不断收到错误computeKnapsack：

"Couldn't match expected type `(t1, t2, t0)' with actual type `[a0]`"

我无法理解问题可能是什么。我正在尝试创建一个包含 3 项元组的列表。我怎样才能让它停止期待单个 3 条目元组？

fst3 (a,b,c) = a
snd3 (a,b,c) = b
trd3 (a,b,c) = c
fst4 (a,b,c,d) = a
snd4 (a,b,c,d) = b
trd4 (a,b,c,d) = c
qud4 (a,b,c,d) = d

sortFrac (a1, b1, c1, d1) (a2, b2, c2, d2)
  | d1 > d2 = GT
  | d1 <= d2 = LT

fracKnap (x:xs) =
    fractionalKnapsack (x:xs) []

fractionalKnapsack (x:xs) fracList =
    if length (x:xs) <= 1
        then computeKnapsack (sortBy sortFrac (((fst3 x),(snd3 x),(trd3 x),(snd3 x) / (trd3 x)):fracList)) 100
        else fractionalKnapsack xs (((fst3 x),(snd3 x),(trd3 x),(snd3 x) / (trd3 x)):fracList)

computeKnapsack (x:xs) weightLeft =
    if length (x:xs) <= 1
        then (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x)))
        else (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))):(computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))
4

3 回答 3

7

结果的then分支中computeKnapsack是单个 3 元组，但在else分支中是 3 元组的列表。

我要computeKnapsack为你重写。我将从修复错误的版本开始：

computeKnapsack (x:xs) weightLeft =
    if length (x:xs) <= 1
        then [(fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x)))]
        else  (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))) : (computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))

首先，我要说如果第一个参数computeKnapsack是空列表会发生什么：

computeKnapsack []     _          = []
computeKnapsack (x:xs) weightLeft =
    (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))) : (computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))

它使我们能够摆脱if-test，使代码整体更短，更容易理解。

接下来，我将解构x：

computeKnapsack []             _          = []
computeKnapsack ((a,b,_,d):xs) weightLeft =
    (a, b, ((floor (weightLeft / d))*d)) : (computeKnapsack xs (weightLeft-(floor (weightLeft / d)*d)))

您可能更愿意遵循 leftaroundabout 的建议来创建具有有意义名称的记录类型。但是如果你继续使用一个元组，通过模式匹配来解构它比使用你的fst4, snd4etc 函数要清楚得多。

同样，代码现在更短且更易于理解，尽管如果我们使用比a、b和更有意义的名称可能会有所帮助d。

我们可以继续这样做：

computeKnapsack []             _          = []
computeKnapsack ((a,b,_,d):xs) weightLeft = (a, b, weight) : (computeKnapsack xs (weightLeft - weight))
  where weight = floor (weightLeft / d) * d

在这里，我发现在两个不同的地方计算了相同的值，并将该值提取到它自己的命名变量中。weight只需要计算一次而不是两次，因此computeKnapsack现在效率略高。更重要的是，我现在明白了computeKnapsack在做什么。

我知道您是 Haskell 的新手。请将此作为有关如何编写更清晰的 Haskell 代码的建设性建议。

于 2012-08-05T17:32:28.850 回答
2

我冒昧地清理了您的computeKnapsack功能，以便您可以更清楚地看到问题：

computeKnapsack (x:xs) weightLeft =
 let e = (fst4 x, snd4 x, floor (weightLeft / qud4 x) * qud4 x)
  in if length (x:xs) <= 1
     then e
     else e:computeKnapsack xs (weightLeft - floor (weightLeft / qud4 x) * qud4 x)

我的改变纯粹是装饰性的。即使在我更改之后，您的computeKnapsack功能仍然会损坏，算法不好，编码风格也不好。

从重写后的版本可以看出，你的if语句有两个分支，一个返回一个元组，另一个返回一个元组列表。您可以简单地通过更改第一个分支以返回具有单个元素的列表来修复它：

computeKnapsack (x:xs) weightLeft =
 let e = (fst4 x, snd4 x, floor (weightLeft / qud4 x) * qud4 x)
  in if length (x:xs) <= 1
     then [e]
     else e:computeKnapsack xs (weightLeft - floor (weightLeft / qud4 x) * qud4 x)

此外，在向 StackOverflow 提交第三个问题之前，请花时间完成 Haskell 的介绍性教程，例如http://learnyouahaskell.com/，这将有助于解决您的许多问题。

于 2012-08-05T17:43:32.483 回答
0

一个问题在fractionalKnapsack. computeKnapsack在该行中，您使用元组而不是作为输入调用函数list。

于 2012-08-05T17:07:13.630 回答