0

I have an assignment to solve the coin change problem which goes like this: i have 5 types of coins {1,5,10,25,50}, We want to make changes with these coins for a given amount of money, in how many ways can i form up 11 cents for example, or n cents in general ? my program should be able to handle up to 7489 cents as an input.

i used recursion and dynamic programming to solve the problem but i get a stack overflow error during runtime at (input >= 3980)

How do i solve this error ?

#include <iostream>
using namespace std;
typedef long long ll;
int Cents[5] = { 1,5,10,25,50 }, in, mem[5][7495];

ll CC(int i, int val) { // this is where the recursion happens
    if (val == 0)   return 1;
    if (i == 5) return 0;
    if (mem[i][val] != -1) return mem[i][val];
    long long op1 = CC(i + 1, val);
    long long op2 = Cents[i] <= val ? CC(i, val - Cents[i]) : 0;
    return  mem[i][val] = (op1+op2);
}

int main() { // here i pass an input and fill the mem 2d array with -1's
    scanf_s("%d", &in);
    memset(mem, -1, sizeof mem);
    printf("%lld\n", CC(0, in));
    system("pause");
    return 0;
}

if the input is 5 for example, then the output should be 2 ways (1),(5) if 11 , then 4 (1*11),(1*6,5*1),(10*1,1*1),(1*1,5*2) and so on.

Improve this question
9
  • Two solutions: 1) Use bottom-up approach, instead of top-down. 2) Check your course instructions about command line arguments. It's possible that they have stack size which is bigger than a default one (see this answer for example: stackoverflow.com/a/2275586/2956272). Commented Aug 15, 2019 at 3:48
  • 1
    The recursion depth for input n is proportional to n, as you are trying to make change in n pennies. Such an approach is unreasonable. Commented Aug 15, 2019 at 3:52
  • You could remove the recursion. Commented Aug 15, 2019 at 4:04
  • memset(mem, -1, sizeof mem) sets each byte in mem to -1. There is no guarantee that this will result in each int value in the mem array having the value -1. Commented Aug 15, 2019 at 13:03
  • Does your assignment require you to use recursion? Doing the calculation in a loop is much simpler and much more flexible. Commented Aug 15, 2019 at 13:04

1 Answer 1

Reset to default
1

You have a stack overflow because your recursion depth is limited by only the size of your array and the number of pennies. And your stack state is reasonable in size.

One solution is to go with an explicit stack.

enum coins {
  penny, nickle, dime, quarter, half,
  coin_count
};
enum {
  max_cash = 7495
};
struct coin_problem {
  coins lowest_coin = penny;
  int money = 0;
};
struct coin_cache {
  unsigned long long solution[coin_count][max_cash+1];
  coin_cache(){
    for(auto& row:solution)
      for(auto& val:row)
        val=-1;
  }
  unsigned long long& set(coin_problem p){
    return solution[p.lowest_coin][p.money];
  }
  unsigned long long get(coin_problem p)const{
    if(p.lowest_coin==coin_count) return 0;
    if(p.money==0) return 0;
    return solution[p.lowest_coin][p.money];
  }
};
unsigned long long count_solutions( std::vector<coin_problem>& vec, coin_cache& cache){
  unsinged long lon retval = 0;
  while(!vec.empty()){
    auto cur = vec.back();
    retval = cache.get[cur];
    if (retval != -1) {
      vec.pop_back();
      continue;
    }
    ++cur.lowest_coin;
    auto op1 = cache.get[cur];
    if (op1 == -1) vec.push_back(cur);
    --cur.lowest_coin;
    unsigned long long op2 = -1;
    if(Cents[cur.lowest_coin] <= cur.money){
      cur.money -= Cents[cur.lowest_coin];
      op2 = cache.get[cur];
      if (op2==-1) vec.push_back(cur);
      cur.money += Cents[cur.lowest_coin];
    } else {
      op2 = 0;
    }
    if (op1 != -1 && op2 != -1){
      retval = cache.set(cur) = op1+op2;
      vec.pop_back();
    }
  }
  return retval;
}
unsigned long long count_solutions( coin_problem p ){
  auto pcache = std::make_unique<coin_cache>();
  std::vector<coin_problem> todo = {p};
  return count_solutions( todo, *pcache );
}

I tore your recursive solution up and gave it a manual stack.

For each entry in the stack of problems, we first see if there is a solution waiting in the cache. If so, we calculate it, and store it in the cache, and pop the problem. If the stack of problems is empty, we return it.

If not, we push sub problems to solve first onto the top if the stack, leaving our current problem to be solved later, and loop until the stack is empty.

As our manual stack exists on the free store (aka the heap) we are unlikely to experience a stack overflow on a desktop system.

This isn't perfectly efficient, as we can have more than one entry on the stack for each problem. But that should be at most a constand factor, and can be likely fixed by reordering the "recursion" to do the "deepest" call first. Or making the stack of problems a set of problems ordered by depth.

Another approach is to just solve every entry in the table, deepest first.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you very much for the help !

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.