1

我一直在玩一个众所周知的背包问题。这一次 - 然而 - 我决定在 F# 中实现它，因为我正在学习该语言并发现它特别有趣。

我已经设法实现了算法的主要部分，但我也需要回溯。不幸的是，我在网上找到的所有信息都使用了 Haskell，我还不知道（还；））。

作为占位符，我使用可变变量实现了回溯（无需详细说明，“组合 (i, k)”返回 i 项和 k 容量的部分解决方案）：

let output = 
    List.rev
        [
            let i = ref N
            let k = ref K
            // analize items starting with the last one
            for item in Array.rev items do
                match !k - item.Size with
                // if size of i-th item is greater than current capacity...
                | x when x <  0 -> i := !i - 1
                       // ... this means we haven't taken this item
                                   yield 0
                // otherwise we've got two cases
                | x when x >= 0 -> let v1 = combinations (!i-1, !k) id
                                   let vc = combinations (!i, !k) id
                                   if v1 = vc then 
                                    // case 1: item hasn't been taken
                                    i := !i - 1
                                    yield 0
                                   else
                                     // case 2: item is contained in the optimal solution
                                    i := !i - 1
                                    k := x
                                    yield 1
        ]

List.iter (fun x -> printf "%A " x) output

我相信在 F# 中有更好的方法来做到这一点（例如使用计算表达式）。我很高兴听到有关如何以功能样式实现此功能的任何提示/信息。

最后一件事：请记住我是函数式编程的新手，并尽量避免像我发现的那样使用一些魔术表达式：

“单子是内函子类别中的一个幺半群，有什么问题？” :)

4

1 回答 1

6

在这种情况下，您可以使用的一般模式是折叠。当您需要遍历列表（例如items，在您的情况下）并在您进行时保持某些状态（i并且k，在您的情况下）时，这很有用。这可以使用高阶函数来实现Array.fold（当您使用数组时）：

let results, _, _ = items |> Array.rev |> Array.fold (fun (resultsSoFar, i, k) item ->
  match k - item.Size with
  // if size of i-th item is greater than current capacity...
  | x when x <  0 -> 
      // ... this means we haven't taken this item
      (0::resultsSoFar, i - 1, k)
  // otherwise we've got two cases
  | x when x >= 0 -> 
      let v1 = combinations (i-1, !k) id
      let vc = combinations (i, !k) id
      if v1 = vc then 
        // case 1: item hasn't been taken
        (0::resultsSoFar, i - 1, k)
      else
        (1::resultsSoFar, i - 1, x) ) ([], N, K)

这个想法是该函数获取先前的状态(resultsSoFar, i, k)和当前状态，item并且应该返回新状态 - 例如，如果我们想要产生0和减少i，我们可以返回(0::resultsSoFar, i - 1, k)，如您在第一种情况中看到的那样。

初始状态是最后一个参数([], N, K)，你得到的结果由所有三个值组成，所以我使用模式来忽略andresults, _, _的最后一个值。ik

请注意，您的代码不完整，因此我无法运行该代码段（可能存在错误！）但我希望它能够展示总体思路。您还可以使用递归函数或递归序列表达式来实现相同的事情（在这两种情况下，您都将状态保留在参数中，并且您将在列表上使用模式匹配来处理它为空或非空的）。

使用递归序列表达式的方法可能更接近您的命令式版本：

let rec lookup (i, k) items = seq {
  match items with
  | [] -> ()
  | item::items ->
      match k - item.Size with
      // if size of i-th item is greater than current capacity...
      | x when x <  0 -> 
          // ... this means we haven't taken this item
          yield 0
          yield! lookup (i - 1, k) items
      // otherwise we've got two cases
      | x when x >= 0 -> 
          let v1 = combinations (i-1, !k) id
          let vc = combinations (i, !k) id
          if v1 = vc then 
            // case 1: item hasn't been taken
            yield 0
            yield! lookup (i - 1, k) items
          else
            yield 1
            yield! lookup (i - 1, x) items }
于 2013-07-03T23:29:48.167 回答