SPOJ 97. Party Schedule | http://www.spoj.com/problems/PARTY/
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 () |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment