我找到了一篇文章:
在 F# 中使用 continuation-passing style with memoization 解决 0-1 背包问题
关于在 F# 中实现的背包问题。当我学习这门语言时,我发现这真的很有趣,并试图对此进行一些调查。这是我制作的代码:
open System
open System.IO
open System.Collections.Generic
let parseToTuple (line : string) =
let parsedLine = line.Split(' ') |> Array.filter(not << String.IsNullOrWhiteSpace) |> Array.map Int32.Parse
(parsedLine.[0], parsedLine.[1])
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
if cache.ContainsKey(x)
then cache.[x]
else
let res = f x
cache.[x] <- res
res
type Item =
{
Value : int
Size : int
}
type ContinuationBuilder() =
member b.Bind(x, f) = fun k -> x (fun x -> f x k)
member b.Return x = fun k -> k x
member b.ReturnFrom x = x
let cont = ContinuationBuilder()
let set1 =
[
(4, 11)
(8, 4)
(10, 5)
(15, 8)
(4, 3)
]
let set2 =
[
(50, 341045); (1906, 4912); (41516, 99732); (23527, 56554); (559, 1818); (45136, 108372); (2625, 6750); (492, 1484)
(1086, 3072); (5516, 13532); (4875, 12050); (7570, 18440); (4436, 10972); (620, 1940); (50897, 122094); (2129, 5558)
(4265, 10630); (706, 2112); (2721, 6942); (16494, 39888); (29688, 71276); (3383, 8466); (2181, 5662); (96601, 231302)
(1795, 4690); (7512, 18324); (1242, 3384); (2889, 7278); (2133, 5566); (103, 706); (4446, 10992); (11326, 27552)
(3024, 7548); (217, 934); (13269, 32038); (281, 1062); (77174, 184848); (952, 2604); (15572, 37644); (566, 1832)
(4103, 10306); (313, 1126); (14393, 34886); (1313, 3526); (348, 1196); (419, 1338); (246, 992); (445, 1390)
(23552, 56804); (23552, 56804); (67, 634)
]
[<EntryPoint>]
let main args =
// prepare list of items from a file args.[0]
let header, items = set1
|> function
| h::t -> h, t
| _ -> raise (Exception("Wrong data format"))
let N, K = header
printfn "N = %d, K = %d" N K
let items = List.map (fun x -> {Value = fst x ; Size = snd x}) items |> Array.ofList
let rec combinations =
let innerSolver key =
cont
{
match key with
| (i, k) when i = 0 || k = 0 -> return 0
| (i, k) when items.[i-1].Size > k -> return! combinations (i-1, k)
| (i, k) -> let item = items.[i-1]
let! v1 = combinations (i-1, k)
let! beforeItem = combinations (i-1, k-item.Size)
let v2 = beforeItem + item.Value
return max v1 v2
}
memoize innerSolver
let res = combinations (N, K) id
printfn "%d" res
0
然而,这个实现的问题是它非常慢(实际上我无法解决 50 个项目和约 300000 容量的问题,我在 C# 中的幼稚实现在不到 1 秒的时间内就解决了这个问题)。
如果我在某个地方犯了错误,你能告诉我吗?或者也许实现是正确的,这只是解决这个问题的低效方法。