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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice Design & Analysis of Algorithms MCQ
- Buy Data Structure Books
- Apply for Computer Science Internship
- Buy Computer Science Books
- Practice Programming MCQs