SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#

The Bytelandian Gold Coins problem, officially published in SPOJ, concerns 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

noun_project_8551 It can be exchanged to three other coins, i.e., coins. Thus,  coin  yields value in bytelandian gold coins.
noun_project_8551 Alternatively, coin can be exchanged for dollars.

Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin .

Algorithm

From the above interpretation, it is evident that the maximum achievable dollars, (from the exchange of coin ) can be computed  as follows.

image

It effectively demonstrates an optimal substructure and therefore, hints to a dynamic programming (DP) technique to solve it. That is, for a coin , the optimal value of dollar is given by the following function.

image

We employ a top-down DP approach, as it seems more efficient than a bottom-up approach in this context. It is due to the fact that a bottom-up approach generally requires an OPT table to persist results of smaller subproblems. As in this case, the value of can be very large (i.e., , a bottom-up DP would require a very large array, and performs more computations.  Hence, for the overlapping subproblems, we employ memoization.

The following code snippet outlines the implementation of Memo.

Full source code of the solution can be downloaded from this gist. Please leave a comment if you have any question/suggestion regarding this post.
Happy problem-solving! noun_project_6324

Advertisements

One thought on “SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#

  1. Pingback: F# Weekly #9, 2013 | Sergey Tihon's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s