fork(1) download
  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
stdin
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
49 26
48 32