fork(1) download
copy 
  1. open System
  2.  
  3. let computeOptCost (budget,N,(opt:int [,]),optFunValue) = 
  4.   let mutable optCost = 0
  5.   for  c=budget downto 0 do 
  6.     if opt.[N,c] = optFunValue then 
  7.       optCost <- c
  8.     else
  9.       ()
  10.   optCost 
  11.  
  12. let computeOptPartySchedule (budget,N,(costs:int[]),(funValues:int[]))  =   
  13.   let OPT = Array2D.zeroCreate (N+1) (budget+1)
  14.  
  15.   for i = 1 to N do        
  16.     for j = 0 to budget do 
  17.       let c_i = costs.[i-1] //cost for the ith party
  18.       let f_i = funValues.[i-1] // fun value associated with ith party
  19.  
  20.       OPT.[i,j] <-
  21.         match j,c_i with 
  22.         | _ when j<c_i -> OPT.[i-1,j]
  23.         | _            -> Math.Max(OPT.[i-1,j],f_i + OPT.[i-1, j-c_i])
  24.  
  25.   // returning (1) summation of all entrance value, 
  26.   //           (2) summation of fun values
  27.   ((budget,N,OPT,OPT.[N,budget])|>computeOptCost, OPT.[N,budget]) 
  28.  
  29.  
  30. // Example Usage:
  31. //(7,2, [|6;5;|],[|1;1;|])|> computeOptPartySchedule
  32.  
  33. //(50,10,[|12;15;16;16;10;21;18;12;17;18;|],[|3;8;9;6;2;9;4;4;8;9|]) |> computeOptPartySchedule
  34. //
  35. //(50,10,[|13;19;16;12;10;12;13;15;11;16;|],[|8;10;8;9;2;8;5;5;7;2|]) |> computeOptPartySchedule
  36.  
  37. //---------------- IO Stuff ------------------- 
  38. let processHeader  () = 
  39.   let s = Console.ReadLine().Split()
  40.   let budget,noOfParties = s.[0]|>int,s.[1]|>int
  41.  
  42.   match budget,noOfParties with 
  43.   | (0,0) -> None 
  44.   | _     -> Some(budget,noOfParties)
  45.  
  46. let parsePartyData  n = 
  47.   let costs = Array.create n 0
  48.   let funValues =  Array.create n 0
  49.  
  50.   for i = 0 to (n-1) do
  51.     System.Console.ReadLine().Split() 
  52.     |> (fun (s:string []) -> (s.[0]|>int,s.[1]|>int))
  53.     |> (fun (x,y) -> costs.[i] <- x; funValues.[i]<-y)
  54.  
  55.   (System.Console.ReadLine()|>ignore) // reading last line that ends this problem instance 
  56.   costs,funValues
  57.  
  58.  
  59. let solve_SPOJ_PARTY () = 
  60.   let rec solvePartyAux() = 
  61.     match processHeader() with 
  62.     | None -> () 
  63.     | Some(budget,n) -> 
  64.  
  65.         parsePartyData n
  66.         |> (fun (costs,funValues) -> (budget, n, costs, funValues))
  67.         |> computeOptPartySchedule 
  68.         |> (fun (optCosts,optFun)  -> printfn "%d %d" optCosts optFun)
  69.         solvePartyAux()
  70.  
  71.   solvePartyAux()
  72.  
  73. solve_SPOJ_PARTY ()
  74.  
Success #stdin #stdout 0.13s 11944KB
comments (?)
stdin
copy 
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0
stdout
copy 
49 26
48 32
https://ideone.com/9Si17o
language:
F# (mono 4.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!