實施F＃回溯

Question

我一直在玩一個衆所周知的揹包問題。這一次 - 但是 - 我決定在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＃中有更好的方法來做到這一點（例如使用計算表達式）。我很樂意聽到關於如何在功能風格中實現這一點的任何提示/信息。

最後一件事：請記住我是新來的函數式編程，並儘量避免一些魔法表情像我發現：「一個單子是endofunctors類別幺半羣，有什麼問題」

:)

Answer 1

您可以在這種情況下使用的一般模式是摺疊。當你需要走過一個列表（例如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)，你會得到包含所有三個值的結果，所以我使用模式results, _, _忽視的i和k最後一個值。

請注意，您的代碼並不完整，所以無法運行代碼段（可能有錯誤！），但我希望它能證明一般的想法。您也可以使用遞歸函數或遞歸序列表達式來實現相同的事情（在這兩種情況下，您都會保留參數中的狀態，並且您可以使用列表中的模式匹配來處理空白時或不空白時的情況）空）。

使用遞歸序列表達的方式或許更接近你的當務之急版本：

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 }