This is a C++ Program that Solves the Bytelandian Gold Coins Problem using Dynamic Programming technique.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin of value n, 0 <= n <= 1000000000. What is the maximum amount of American dollars you can get for it?

This is a Dynamic programming problem. We can observe that for amount upto 8, we can’t get more money by dividing (into n/2, n/3 and n/4). We will create an array to memoize the values. For any value, min. amount we can get out of it=n. We will compare this value with the value we get after dividing n and select the bigger value.

Case-1:

Amount of Bytelandian coin=8 Maximum amount of american dollars which can be made out of it=8

Case-2:

Amount of Bytelandian coin=25 Maximum amount of american dollars which can be made out of it=27

Case-3:

Amount of Bytelandian coin=520 Maximum amount of american dollars which can be made out of it=576

Here is source code of the C++ Program to Solve the Bytelandian gold coins problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`//bytelandian gold coins`

`#include<bits/stdc++.h>`

using namespace std;

long long int calculate(vector<long long int> &dp, long long int n)

`{`

if(n<10)

return n;

if(n<1000000)

`{`

if(dp[n])

return dp[n];

`else`

`{`

`//now, calculate`

long long int x=calculate(dp, n/2)+calculate(dp, n/3)+calculate(dp, n/4);

dp[n]=max(n,x);

return dp[n];

`}`

`}`

long long int x=calculate(dp, n/2)+calculate(dp, n/3)+calculate(dp, n/4);

return max(n,x);

`}`

int main()

`{`

long long int i,j,k,n;

long long int x,y,z;

int t;

vector<long long int> dp(1000000,0);

cout<<"Enter the amount of bytelandian coin you have ?"<<endl;

cin>>n;

cout<<"Maximum amount of american dollars you can make from this is "<<endl;

cout<<calculate(dp,n)<<endl;

return 0;

`}`

In the main function, we take the amount of the bytelandian coin we have. Then, we invoke the calculate function. the calculate function will compute the maximum amount of american dollars we can make out of this and return this value. The output will be displayed on the standard output.

Case-1: $ g++ bytelandian_gold_coins.cpp $ ./a.out Enter the amount of bytelandian coin you have ? 8 Maximum amount of american dollars you can make from this is 8 Case-2: $ ./a.out Enter the amount of bytelandian coin you have ? 25 Maximum amount of american dollars you can make from this is 27 Case-3: $ ./a.out Enter the amount of bytelandian coin you have ? 520 Maximum amount of american dollars you can make from this is 689

**Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.**

To practice all Dynamic Programming Problems, __here is complete set of 100+ Problems and Solutions__.