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)であり、3 つの値すべてで構成される結果が得られるため、パターンを使用して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 に答える