3
$\begingroup$

The question is motivated by this post on StackOverflow.

Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a sum of elements of $ds$ up to order. Sometimes $f(n, ds)$ is referred to as the number of ways to make change of $n$ in terms of coins with denominations $ds$. For example:

  • $f(1, [1]) = 1$
  • $f(2, [1, 2]) = 2$
  • $f(100, [1, 2]) = 51$
  • $f(5, [1, 2, 5]) = 4$
  • $f(27, [1, 5, 10]) = 12$
  • $f(7, [3, 5]) = 0$

Question: is it possible to compute $f(n, ds)$ in $O(\operatorname{length}(ds))$ time if integer operations take constant time, e.g. $a \bmod b$ can be computed in $O(1)$?

$\endgroup$
2
  • 1
    $\begingroup$ I think this or that could help. It seems solutions are at best in $O(n|ds|)$. $\endgroup$ – Nathaniel May 15 at 11:22
  • $\begingroup$ There are "lists of integers" where the greedy algorithm can be proven optimal. en.wikipedia refers to Pearson, David: A polynomial-time algorithm for the change-making problem, OR Letters 33 (2005). $\endgroup$ – greybeard May 15 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.