open System.IO
open System.Collections.Generic

type Tup = {x: int; y: int}
// define a function "tup" to make it easier to change implementation and benchmark
let inline tup(x, y) = {x=x; y=y}

[<EntryPoint>]
let main (args : string[]) =
    let g_maxSize = 4480
    let fileSizes = [ 1 .. 99 ]

    let optimalResults = new Dictionary<_,_>()
    let lastStep = new Dictionary<_,_>()

    let FetchOrZero (dict:Dictionary<_,_>) k =
        match (dict.TryGetValue k) with
        | true, v -> v
        | _       -> 0

    let files = List.mapi (fun i x -> (i,x)) fileSizes
    for containerSize in 0 .. g_maxSize do
        for (idx,fileSize) in files do
            // We will index the "optimalResults" via tuples:
            let cellCurrent = tup(containerSize, idx)              // The current cell
            let cellOnTheLeftOfCurrent = tup(containerSize, idx-1) // The cell on our left
            // Does the file on column "idx" fit inside containerSize?
            if containerSize<fileSize then
                // it doesn't fit in containerSize
                // so copy optimal value from the cell on its left
                optimalResults.[cellCurrent] <- FetchOrZero optimalResults cellOnTheLeftOfCurrent
                // Copy last step from cell on the left...
                lastStep.[cellCurrent] <- FetchOrZero lastStep cellOnTheLeftOfCurrent
            else
                // It fits!
                // Using file of column "idx", the remaining space is...
                let remainingSpace = containerSize - fileSize
                // and for that remaining space, the optimal result
                // using the first idx-1 files has been found to be:
                let optimalResultOfRemainingSpace = FetchOrZero optimalResults (tup(remainingSpace,(idx-1)))
                // so let's check: do we improve things by using "idx"?
                if optimalResultOfRemainingSpace + fileSize > FetchOrZero optimalResults cellOnTheLeftOfCurrent then
                    // we improved the best result, store it!
                    optimalResults.[cellCurrent] <- optimalResultOfRemainingSpace + fileSize
                    // Store last step - i.e. using file "idx"
                    lastStep.[cellCurrent] <- fileSize
                else
                    // no improvement by using "idx" - copy from left...
                    optimalResults.[cellCurrent] <- FetchOrZero optimalResults cellOnTheLeftOfCurrent
                    // Copy last step from cell on the left...
                    lastStep.[cellCurrent] <- FetchOrZero lastStep cellOnTheLeftOfCurrent

    printfn "Attainable: %d" (FetchOrZero optimalResults (tup(g_maxSize,fileSizes.Length-1)))

    // Navigate backwards... starting from the optimal result:
    let rightMostIndex = fileSizes.Length-1
    let mutable total = FetchOrZero optimalResults (tup(g_maxSize, rightMostIndex))
    while total>0 do
       // The last step we used to get to "total" was...
       let lastFileSize = lastStep.[tup(total, rightMostIndex)]
       printfn "%d removing %d" total lastFileSize
       // And the one before the last step was... (loop)
       total <- total - lastFileSize
    0