SPOJ 97. Party Schedule | http://www.spoj.com/problems/PARTY/

party.fs

open System
  
let computeOptCost (budget,N,(opt:int [,]),optFunValue) = 
  let mutable optCost = 0
  for  c=budget downto 0 do 
    if opt.[N,c] = optFunValue then 
      optCost <- c
    else
      ()
  optCost 
 
let computeOptPartySchedule (budget,N,(costs:int[]),(funValues:int[]))  =   
  let OPT = Array2D.zeroCreate (N+1) (budget+1)
  
  for i = 1 to N do        
    for j = 0 to budget do 
      let c_i = costs.[i-1] //cost for the ith party
      let f_i = funValues.[i-1] // fun value associated with ith party
      
      OPT.[i,j] <-
        match j,c_i with 
        | _ when j<c_i -> OPT.[i-1,j]
        | _            -> Math.Max(OPT.[i-1,j],f_i + OPT.[i-1, j-c_i])
  
  // returning (1) summation of all entrance value, 
  //           (2) summation of fun values
  ((budget,N,OPT,OPT.[N,budget])|>computeOptCost, OPT.[N,budget]) 


// Example Usage:
//(7,2, [|6;5;|],[|1;1;|])|> computeOptPartySchedule

//(50,10,[|12;15;16;16;10;21;18;12;17;18;|],[|3;8;9;6;2;9;4;4;8;9|]) |> computeOptPartySchedule
//
//(50,10,[|13;19;16;12;10;12;13;15;11;16;|],[|8;10;8;9;2;8;5;5;7;2|]) |> computeOptPartySchedule

//---------------- IO Stuff ------------------- 
let processHeader  () = 
  let s = Console.ReadLine().Split()
  let budget,noOfParties = s.[0]|>int,s.[1]|>int

  match budget,noOfParties with 
  | (0,0) -> None 
  | _     -> Some(budget,noOfParties)

let parsePartyData  n = 
  let costs = Array.create n 0
  let funValues =  Array.create n 0

  for i = 0 to (n-1) do
    System.Console.ReadLine().Split() 
    |> (fun (s:string []) -> (s.[0]|>int,s.[1]|>int))
    |> (fun (x,y) -> costs.[i] <- x; funValues.[i]<-y)
  
  (System.Console.ReadLine()|>ignore) // reading last line that ends this problem instance 
  costs,funValues


let solve_SPOJ_PARTY () = 
  let rec solvePartyAux() = 
    match processHeader() with 
    | None -> () 
    | Some(budget,n) -> 
        
        parsePartyData n
        |> (fun (costs,funValues) -> (budget, n, costs, funValues))
        |> computeOptPartySchedule 
        |> (fun (optCosts,optFun)  -> printfn "%d %d" optCosts optFun)
        solvePartyAux()

  solvePartyAux()

solve_SPOJ_PARTY ()