Skip to content

Instantly share code, notes, and snippets.

Created May 1, 2011 18:49
Show Gist options
  • Save anonymous/950728 to your computer and use it in GitHub Desktop.
Save anonymous/950728 to your computer and use it in GitHub Desktop.
let g_maxSize = 4480
let fileSizes = [|1 .. 99|]
let optimalResults = Array.init (g_maxSize+1) (fun _ -> Array.create fileSizes.Length 0)
let lastStep = Array.init (g_maxSize+1) (fun _ -> Array.create fileSizes.Length 0)
for containerSize=0 to g_maxSize do
let optimalResultsContainerSize = optimalResults.[containerSize]
let lastStepContainerSize = lastStep.[containerSize]
for idx=0 to fileSizes.Length-1 do
let fileSize = fileSizes.[idx]
let optimalResultsContainerSizeOnLeft = if idx=0 then 0 else optimalResultsContainerSize.[idx-1]
let lastStepContainerSizeOnLeft = if idx=0 then 0 else lastStepContainerSize.[idx-1]
// 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
optimalResultsContainerSize.[idx] <- optimalResultsContainerSizeOnLeft
// Copy last step from cell on the left...
lastStepContainerSize.[idx] <- lastStepContainerSizeOnLeft
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 = if idx=0 then 0 else optimalResults.[remainingSpace].[idx - 1]
// so let's check: do we improve things by using "idx"?
if optimalResultOfRemainingSpace + fileSize > optimalResultsContainerSizeOnLeft then
// we improved the best result, store it!
optimalResultsContainerSize.[idx] <- optimalResultOfRemainingSpace + fileSize
// Store last step - i.e. using file "idx"
lastStepContainerSize.[idx] <- fileSize
else
// no improvement by using "idx" - copy from left...
optimalResultsContainerSize.[idx] <- optimalResultsContainerSizeOnLeft
// Copy last step from cell on the left...
lastStepContainerSize.[idx] <- lastStepContainerSizeOnLeft
printfn "Attainable: %d" (optimalResults.[g_maxSize].[fileSizes.Length - 1])
// Navigate backwards... starting from the optimal result:
let rightMostIndex = fileSizes.Length-1
let mutable total = optimalResults.[g_maxSize].[rightMostIndex]
while total > 0 do
// The last step we used to get to "total" was...
let lastFileSize = lastStep.[total].[rightMostIndex]
printfn "%d removing %d" total lastFileSize
// And the one before the last step was... (loop)
total <- total - lastFileSize
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment