Contents tagged with DynamicProgramming
-
Solving SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#
The Bytelandian Gold Coins problem, officially published in SPOJ, is centered around computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.
Interpretation
The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin--
It can be exchanged to three other coins, i.e.,coins. Thus, coin
value in bytelandian gold coins.
Alternatively, Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin -
UVa 10664. Luggage with Dynamic Programming
The UVa 10664: Luggage is a typical example of the problems that can be solved using dynamic programming (DP) technique. In fact, after further analysis, this problem can be realized as a special case of Subset-Sum problem, which we have discussed in a recent post.
-
Solving SPOJ 97. Party Schedule with Dynamic Programing and 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
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
have costs
such that
is as large as possible, and subject to the following restriction-- (read more)
-
Solving Subset Sum with Dynamic Programming and F#
The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in
time complexity, given that
is the number of elements in the set. This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution...(read more)
-
Levenshtein Distance with F#
Definition. Edit Distance—a.k.a “Lavenshtein Distance”--is the minimum number of edit operations required to transform one word into another. The allowable edit operations are letter insertion, letter deletion and letter substitution ...(read more)
