SPOJ 97. Party Schedule (PARTY) with F#

The Party Schedule problem, published in SPOJ website, is about deriving an optimal set of parties that maximizes fun value, given a party budget: and parties: where each party have an entrance cost , and is associated with a fun value .

In this post, we discuss how to solve this problem by first outlining an algorithm, and afterwards, by implementing that using F#.

Background¶

This problem is a special case of  Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed .

More formally, we are given a budget as the bound. All parties have costs and values . We have to select a subset such that is as large as possible, and subject to the following restriction —

Furthermore, an additional constraint: “do not spend more money than is absolutely necessary” is applied, which implies following. Consider two parties and ; if and , then we must select instead of .

Algorithm¶

Attempt 1

The definition of this problem suggests a recursive solution. However, a naïve recursive solution is quite impractical in this context, as it requires exponential time due to the following reason: a naïve recursive implementation applies a top-down approach that solves the subproblems again and again.

Attempt 2

Next, we select dynamic programming technique to solve this problem. So, we have to define a recurrence that expresses this problem in terms of its subproblems, and therefore it begs the answer of the following question:

What are the subproblems? We have two variants: and , i.e. available budget and number of parties. We can derive smaller subproblems, by modifying these variants; accordingly, we define-

It returns the maximum value over any subset where . Our final objective is to compute , which refers to the optimal solution, i.e., maximal achievable fun value from budget and parties.

To define the recurrence, we describe in terms of its smaller subproblems.

How can we express this problem using its subproblems? Let’s denote to be the optimal subset that results in . Consider party and note following.

1. It , then . Thus, using the remaining budget and the parties , we seek the optimal solution.
2. Otherwise, then . Since is not included, we haven’t spent anything from .

Obviously, when , we apply the 2nd case. Using the above observations, we define the recurrence as follows–

where the base conditions can be rendered as below.

Using the above recurrence, we can compute for all parties and for costs . In essence, we build the OPT table, which consists of rows and columns, using a bottom-up approach as stated in the following algorithm.

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
 Initialize OPT[0,c] = 0, for c = 0..C and OPT[i,0], for i= 0..n For i = 1,...,n do For c = 1,..,C do Use above recurrence to compute OPT(i,c) Return OPT(n,C)
view raw gistfile1.txt hosted with ❤ by GitHub

Implementation¶

Following code builds the OPT table using the stated algorithm.

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
 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 OPT.[i-1,j] | _ -> Math.Max(OPT.[i-1,j],f_i + OPT.[i-1, j-c_i]) // returning (1) summation of all entrance fee or costs, // (2) summation of fun values ((budget,N,OPT,OPT.[N,budget])|>computeOptCost, OPT.[N,budget])
view raw gistfile1.fs hosted with ❤ by GitHub

In effect, it does two things: builds OPT table and afterwards, returns the OPT(n,C) and associated optimal cost (due to the constraint “do not spend more money than is absolutely necessary” discussed in background section)  as a tuple (see Line 16). Following function computes the optimal cost.

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
 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
view raw gistfile1.fs hosted with ❤ by GitHub

Complexity.  as each requires time.

For the complete source code, please check out this gist,  or visit its IDEONE page to play with the code. Please leave a comment if you have any question or suggestion regarding the algorithm/implementation.

Happy coding!