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#. 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--
(read more)