我们必须为一个学校的项目用不同的编程类型对背包问题进行编程。一种是函数式编程,我正在尝试用F#编程。
我使用一个递归函数,总是得到具有最高值的项目放入我的背包。在最后我希望所有元素的总价值最高的组合。这是Python中的解决方案,我只是希望能把它转移到F#中。
let names = ["Zahnbürste","Zahnpasta", "Teller", "Duschgel", "Shampoo", "Handtuch", "Besteck", "Trinkflasche", "Becher", "Taschenlampe", "Sonnenschutz", "Medikamente"]
let volumes = [2,4,5,2,2.5,10,5,3,3,9,2,1]
let values = [3,19,17,15,13,3,2,8,5,6,17,15]
maxVol = 20;
def rucksackProblem(restVol, i) :
if (i < (len(volumes))) :
dontPack = rucksackProblem(restVol, i + 1)
pack = 0
if (restVol - volumes[i] >= 0) :
pack = values[i] + rucksackProblem(restVol - volumes[i], i + 1)
if (dontPack > pack) :
return dontPack
else :
return pack
else :
return 0
result = rucksackProblem(maxVol, 0)
print(result)
这是我在F#中尝试的。请帮我弄清楚我的问题。我是F#和函数式编程的新手,其他解决knapsack问题的方法有几百行代码,似乎过于复杂。这并没有真正打印出我想从这个函数得到的最终结果。它只是返回0。
open System
let names_list = ["Zahnbürste";"Zahnpasta"; "Teller"; "Duschgel";"Shampoo"; "Handtuch"; "Besteck"; "Trinkflasche"; "Becher";"Taschenlampe";"Sonnenschutz";"Medikamente"]
let volumes_list = [2;4;5;2;3;10;5;3;3;9;2;1]
let values_list = [3;19;17;15;13;3;2;8;5;6;17;15]
let maxVolume = 20
let rec rucksackProblem (restVol : int, i : int) =
if i < volumes_list.Length then
let dontPack = rucksackProblem(restVol, i + 1)
let pack = 0
let currentVolumeItem = volumes_list.Item(i)
if restVol - volumes_list.Item(i) >= 0 then
let mutable pack = values_list.Item(i) + rucksackProblem(restVol - volumes_list.Item(i), i + 1)
printf "%i" (volumes_list.Item(i))
else()
if dontPack > pack then
dontPack
else
pack
else
0
let result = rucksackProblem(maxVolume, 0)
printfn "%i" result
Console.ReadKey() |> ignore
我不能保证算法的正确性和效率,但这应该可以做到你要找的东西。
open System
let names_list = ["Zahnbürste";"Zahnpasta"; "Teller"; "Duschgel";"Shampoo"; "Handtuch"; "Besteck"; "Trinkflasche"; "Becher";"Taschenlampe";"Sonnenschutz";"Medikamente"]
let volumes_list = [2;4;5;2;3;10;5;3;3;9;2;1]
let values_list = [3;19;17;15;13;3;2;8;5;6;17;15]
let maxVolume = 20
let rec rucksackProblem (restVol : int) (i : int) =
if i < volumes_list.Length then
let dontPack = rucksackProblem restVol (i + 1)
let currentVolumeItem = volumes_list.[i]
let pack =
if restVol - volumes_list.[i] >= 0 then
values_list.[i] + rucksackProblem (restVol - volumes_list.[i]) (i + 1)
else 0
if dontPack > pack then
dontPack
else
pack
else
0
let result = rucksackProblem maxVolume 0
printfn "%i" result
请注意,因为你的可变包是在if的范围内定义的 在if的分支之外是无法访问的。 我把这个定义移到了上面,这样它就可以在外面被访问了。
我还做了一些其他的改动。 在F#中,列表中的项目可以以list.[index]的形式被访问。 参数的传递用空格而不是逗号隔开,因为这是一种更灵活的方法,例如允许用 咖喱.
我冒昧地重写了你的代码,最后得到的是这样的结果。
let names = ["Zahnbürste"; "Zahnpasta"; "Teller"; "Duschgel"; "Shampoo"; "Handtuch"; "Besteck"; "Trinkflasche"; "Becher"; "Taschenlampe"; "Sonnenschutz"; "Medikamente"]
let weights = [2; 4; 5; 2; 3; 10; 5; 3; 3; 9; 2; 1]
let profits = [3; 19; 17; 15; 13; 3; 2; 8; 5; 6; 17; 15]
let cap = 20
type Product = { Name: string; Profit: int; Weight: int }
let knappsack names profits weights cap =
let sortItemsInDecreasingOrder =
List.zip3 names profits weights
|> List.map (fun x -> { Name=x.Item1; Profit=x.Item2; Weight=x.Item3 })
|> List.sortBy (fun p -> p.Profit / p.Weight)
|> List.rev
let products = sortItemsInDecreasingOrder
let rec pack bag totalWeight idx =
if idx > List.length names - 1 then bag
else
let p = products.[idx]
if (totalWeight + p.Weight) > cap then bag
else
pack (bag @ [p]) (totalWeight + p.Weight) (idx + 1)
pack List.empty 0 1
knappsack names profits weights cap
|> Dump
|> ignore
我得到的结果是
名称 利润 重量 Sonnenschutz 17 2 Duschgel 15 2 Shampoo 13 3 Zahnpasta 19 4 Teller 17 5 Trinkflasche 8 3 89 19
另外,如果你有兴趣学习使用f#的函数式编程,我可以强烈推荐你使用 https:/fsharpforfunandprofit.com.