I'm creating a program that returns the least quantity of sums required to get to a number (n) using only 1, 2, 6 and 13. It works perfectly for small values of n, but once n gets to values like 200 it takes the program too much time to calculate the result.
Therefore, I have two questions:
1. Is there any way to make the recursion faster?
2. Should I avoid using recursion and use a loop instead?
Here's the commented code:
#include <iostream>
#define MAX 500000
using namespace std;
void cal(int inp, int &mini, int counter = 0);
int main (void)
{
//Gets input
int n;
cin >> n;
//Defines mini as the MAX result we can get
int mini = MAX;
//Calls the function
cal(n, mini);
//Prints the best result
cout << mini << endl;
return 0;
}
void cal(int inp, int &mini, int counter)
{
//Breaks recursion if it finds an answer
if(!inp)
{
if(counter<mini) mini = counter;
return;
}
//Breaks recursion if the input is negative
//or the counter is more than the best result
else if((inp<0) || (counter>mini)) return;
//Counts amount of recursions
counter++;
//Tries every combination
cal(inp-13, mini, counter);
cal(inp-6, mini, counter);
cal(inp-2, mini, counter);
cal(inp-1, mini, counter);
return;
}
Thank you
The problem is your brute force. Let me suggest something better:
Preliminaries: If you have two 1s, it is always better to use a 2. If you have three 2s, it is better to use a 6. If you have thirteen 6s, it is better to use six thirteens.
So the any admissable sum will always look like n = 13m+k where k is written as a sum of 1, 2, and 6. With the preliminaries, we know that for the optimal sum k will never exceed 1+2*2+12*6 = 77. (The reverse doesn't hold. Not any number below 78 is best written without 13s of course.) So brute forcing those is good enough. You can then use a lookup table.
This could still be optimized further, but it should not break down at 200.
Assuming you have found your first 77 entries (which can be optimized as well) you can do this (still unoptimized ;-):
int num_13 = ((n-78) / 13) + 1;
int sum_length = MAX;
for (i = num_13; i*13 < n; i++) {
int tmp = entries_77[n-i*13]+i;
if (tmp < sum_length) {
num_13 = i;
sum_length = tmp;
}
}
I would be even quicker to compile an array for the equivalence classes modulo 13, since for any given equivalence class any number exceeding 78 will have the same k.
You can use DP (Dynamic Programming) approach to solve your problem. It's well known Coins Problem
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With