Guest User

Untitled

a guest
May 1st, 2011
273
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. open System.IO
  2. open System.Collections.Generic
  3.  
  4. type Tup = {x: int; y: int}
  5. // define a function "tup" to make it easier to change implementation and benchmark
  6. let inline tup(x, y) = {x=x; y=y}
  7.  
  8. [<EntryPoint>]
  9. let main (args : string[]) =
  10.     let g_maxSize = 4480
  11.     let fileSizes = [ 1 .. 99 ]
  12.  
  13.     let optimalResults = new Dictionary<_,_>()
  14.     let lastStep = new Dictionary<_,_>()
  15.  
  16.     let FetchOrZero (dict:Dictionary<_,_>) k =
  17.         match (dict.TryGetValue k) with
  18.         | true, v -> v
  19.         | _       -> 0
  20.  
  21.     let files = List.mapi (fun i x -> (i,x)) fileSizes
  22.     for containerSize in 0 .. g_maxSize do
  23.         for (idx,fileSize) in files do
  24.             // We will index the "optimalResults" via tuples:
  25.             let cellCurrent = tup(containerSize, idx)              // The current cell
  26.             let cellOnTheLeftOfCurrent = tup(containerSize, idx-1) // The cell on our left
  27.             // Does the file on column "idx" fit inside containerSize?
  28.             if containerSize<fileSize then
  29.                 // it doesn't fit in containerSize
  30.                 // so copy optimal value from the cell on its left
  31.                 optimalResults.[cellCurrent] <- FetchOrZero optimalResults cellOnTheLeftOfCurrent
  32.                 // Copy last step from cell on the left...
  33.                 lastStep.[cellCurrent] <- FetchOrZero lastStep cellOnTheLeftOfCurrent
  34.             else
  35.                 // It fits!
  36.                 // Using file of column "idx", the remaining space is...
  37.                 let remainingSpace = containerSize - fileSize
  38.                 // and for that remaining space, the optimal result
  39.                 // using the first idx-1 files has been found to be:
  40.                 let optimalResultOfRemainingSpace = FetchOrZero optimalResults (tup(remainingSpace,(idx-1)))
  41.                 // so let's check: do we improve things by using "idx"?
  42.                 if optimalResultOfRemainingSpace + fileSize > FetchOrZero optimalResults cellOnTheLeftOfCurrent then
  43.                     // we improved the best result, store it!
  44.                     optimalResults.[cellCurrent] <- optimalResultOfRemainingSpace + fileSize
  45.                     // Store last step - i.e. using file "idx"
  46.                     lastStep.[cellCurrent] <- fileSize
  47.                 else
  48.                     // no improvement by using "idx" - copy from left...
  49.                     optimalResults.[cellCurrent] <- FetchOrZero optimalResults cellOnTheLeftOfCurrent
  50.                     // Copy last step from cell on the left...
  51.                     lastStep.[cellCurrent] <- FetchOrZero lastStep cellOnTheLeftOfCurrent
  52.  
  53.     printfn "Attainable: %d" (FetchOrZero optimalResults (tup(g_maxSize,fileSizes.Length-1)))
  54.  
  55.     // Navigate backwards... starting from the optimal result:
  56.     let rightMostIndex = fileSizes.Length-1
  57.     let mutable total = FetchOrZero optimalResults (tup(g_maxSize, rightMostIndex))
  58.     while total>0 do
  59.        // The last step we used to get to "total" was...
  60.        let lastFileSize = lastStep.[tup(total, rightMostIndex)]
  61.        printfn "%d removing %d" total lastFileSize
  62.        // And the one before the last step was... (loop)
  63.        total <- total - lastFileSize
  64.     0
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×