0

到目前为止，我正在尝试在 haskell 中解决分数背包问题

代码：

{- Input "how much can the knapsack hole <- x" "Possible items in sack [(label, value, weight), ...]" -}
knap x [] = []
knap x y = if length y == 1 then

输入列表的形式为 [([Char], Integer, Integer), ... ] 列表列表（字符列表、整数和整数）。

我的问题是试图找出可能放入背包的每件物品的标签、价值和重量。（从列表列表中提取值）

在我的前奏>提示中，我正在做一些尝试

ghci 输出：

Prelude> let x = [("label 1", 2, 14), ("label 2", 1, 15)]
Prelude> :t x
x :: [([Char], Integer, Integer)]
Prelude> length x
2
Prelude> x !! 0
("label 1",2,14)
Prelude> x !! 0 !! 1

<interactive>:1:1:
    Couldn't match expected type `[a0]'
                with actual type `([Char], Integer, Integer)'
    Expected type: [[a0]]
      Actual type: [([Char], Integer, Integer)]
    In the first argument of `(!!)', namely `x'
    In the first argument of `(!!)', namely `x !! 0'

如您所见，我正在尝试做清单！指数 ！！尝试从“项目”中拉出重量的索引。执行此操作的正确语法是什么？

4

2 回答 2

2

(a,b,c)是一个元组，而不是一个列表。你不能!!在元组上使用。毕竟：!!元组的类型是什么？

从元组中获取值的方法是使用这样的模式匹配：

let (name, x, y) = theTuple in
-- ...

模式匹配通常也是获得列表头部的首选方式。因此，处理元组列表的函数通常看起来像这样：

f [] = -- handle the empty list
f ((name, x, y) : rest) =
  -- do something with name, x and y and then recurse on rest
于 2012-07-30T17:17:03.870 回答
2

好吧，该!!运算符仅适用于列表，正如您从其类型签名中看到的那样：[a] -> Int -> a.

如果您想坚持使用元组，您可以为 3 元组定义自己的函数，其风格为fst和snd。您可以通过模式匹配来做到这一点；就像是：

first :: (a,b,c) -> a
first (a,_,_) = a

但是，最好为项目设计数据类型，并使用记录来提取您需要的字段。

data Item = Item { label  :: String
                   value  :: Int
                   weight :: Int
                 }

然后制作一个x可以使用的新项目let x = Item {label = "label 1", value = 2, weight = 14}

Now you could model your knapsack as a list of items of type [Item], and to get the value of the first item, you could use value $ knapsack !! 0, where knapsack is your list of items.

于 2012-07-30T17:20:03.017 回答