A solution to the knapsack problem using a dynamic algorithm

dynamicKnapsack.fsx

// KNAPSACK

/// weight should be minimised and price maximised
type Object = {weight : int ; price : int ; id : int}
type State = {weight : int ; price : int ; objects : Object list}
let emptyState = {weight=0 ; price=0 ; objects=[]} 

/// returns a list of object wich maximise the price while keeping sum(weight) <= maxWeight
/// solution using dynamic programming
/// might explode if maxWeight gets too big : can be avoided by dividing the weights (aproximate solution)
let knapsackDyn maxWeight (objects : Object list) =
  let mutable previousSolution = emptyState
  let solution = Array.create (maxWeight+1) emptyState 
  for ob in objects do 
    previousSolution <- solution.[ob.weight-1]
    for i = ob.weight to maxWeight do 
       let newWeight = previousSolution.weight + ob.weight
       let newPrice = previousSolution.price + ob.price
       if (newPrice > solution.[i].price) && (newWeight <= i) then 
          let newSolution = {weight = newWeight ; price = newPrice ; objects = ob :: previousSolution.objects}
          previousSolution <- solution.[i]
          solution.[i] <- newSolution
       else previousSolution <- solution.[i]
  solution.[maxWeight]