Задача о рюкзаке на F # с рекурсивной функцией - PullRequest
Новая
       101

Задача о рюкзаке на F # с рекурсивной функцией

1 голос
/ 17 июня 2020

Нам нужно запрограммировать задачу о рюкзаке для школьного проекта с разными типами программирования. Один из них - функциональное программирование, и я пробую его на 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 #, и функциональное программирование и другие решения проблемы с рюкзаком с сотнями строк кода кажутся чрезмерно сложными. На самом деле это не печатает конечный результат, который я хочу получить от этой функции. Он просто возвращает 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

Ответы [ 2 ]

0 голосов
/ 17 июня 2020

Я взял на себя смелость переписать ваш код и закончил с этим. 


    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

Результат, который я получаю: 

    Name            Profit  Weight
    Sonnenschutz    17      2 
    Duschgel        15      2 
    Shampoo         13      3 
    Zahnpasta       19      4 
    Teller          17      5 
    Trinkflasche    8       3 
                    89      19

Кстати. Если вы заинтересованы в изучении функционального программирования с использованием f #, я настоятельно рекомендую https://fsharpforfunandprofit.com/.

0 голосов
/ 17 июня 2020

Я не могу поручиться за правильность или эффективность алгоритма, но он должен делать то, что вы ищете: 

 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. Я переместил это определение выше, чтобы к нему можно было получить доступ извне.

Я также внес несколько других изменений. В F # элементы списка доступны как list. [Index]. Параметры передаются через пробелы, а не через запятую, поскольку это более гибкий подход, например, позволяет каррирование .

...