1

Given a number $n$ (integer) I should find $a_1,\ldots,a_k$ such that $k$ is minimal and $n=a_1!+\cdots+a_k!$.

I think that the following greedy algorithm should give the solution - iterating over $1!,\ldots,k!$ I find the biggest k such that $k!\leq n$ and then the solution is $1+{}$solution for $n-k!$.

I'm new to proving such algorithms and I've read that at first I should prove that there exists optimal sum containing $k!$ by picking an arbitrary optimal solution and exchanging something else with $k!$ and prove that the solution remains optimal after this operation. But I don't see how that could be done here. Any hints?

Michael Hardy
  • 1
qiubit
  • 2,313
  • 4
    It might be easier to prove in a slightly generalized form. You're taking the sequence of "denominations" ${j!}$ and proving that the greedy algorithm always lets you make $n$ dollars with the fewest "bills". Generalize ${j!}$ to any sequence ${d_j}$ where $d_1=1$ and $d_j$ always divides $d_{j+1}$. You might also consider looking at the number of smallest bills rather than the number of largest bills when you reduce the problem inductively. – Greg Martin Jan 18 '15 at 19:11

0 Answers0