Bytelandian Gold Coins Problem - Dynamic Programming Solutions

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

Problem Description

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?

Problem Solution

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.

Expected Input and Output

Case-1:

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

Case-2:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

 
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

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

« Prev - Non Decreasing Digits Problem – Dynamic Programming Solutions

» Next - Assignments Problem – Dynamic Programming Solutions

Related Posts:

Apply for Computer Science Internship
Practice Programming MCQs
Check Programming Books
Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: