SPOJ 97. Party Schedule | http://www.spoj.com/problems/PARTY/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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