4
$\begingroup$

The change-making problem with unbounded repetition is:

  • Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$ and an amount $v$.
  • Output: Can the given $v$ amount of money be made with these coins?

The first recurrence is based on the subproblems of $C[w]$: can $w$ be made with these coins?

$$ C[w] = \bigvee_{i: x_i \le w} C[w-x_i]. $$

The second recurrence is based on the subproblems of $C[i,w]$: can $w$ be made with coins $x_1, \ldots, x_i$?

$$ C[i,w] = (C[i, w-x_i] \land w \ge x_i) \lor C[i-1, w]. $$ The recurrence consider both cases of whether $x_i$ is used or not.


Problem: I think both recurrences are correct. Therefore, I want to understand their connections.

Specifically, how are they equivalent (if both are correct, of course) in terms of the subproblems they solve.

Can we transform one to another by, for instance, introducing a second variable to the first one or eliminating one variable from the second one?

$\endgroup$
3
$\begingroup$

First, the number of subproblems and dependencies among these subproblems for the first recurrence are $v$ and $nv$ respectively, while they are $nv$ and $2nv$ respectively for the second one.

Pictorially, the subproblem-dependency graph of the first recurrence is a 1D array and that of the second one is a 2D table.

Informally, the subproblem-dependency graph of the second recurrence can be regarded as a "compacted" version of that of the first one in the sense that the 2D table is compressed into a 1D array through the clause $\lor C[i−1,w]$ in the second recurrence.

Formally, inspired by the comment made by @Raphael, if we expand $C[i−1,w]$ recursively in the second recurrence, we get (ignoring the $w \ge x_i$ details)

$$ \begin{align*} C[i,w] &= C[i, w-x_i] \lor C[i-1, w] \\ &= C[i, w-x_i] \lor (C[i-1, w-x_{i-1}] \lor C[i-2, w]) \\ &= C[i, w-x_i] \lor C[i-1, w-x_{i-1}] \lor C[i-2, w-x_{i-2}] \lor C[i-3, w] \\ &= \cdots \\ &= \bigvee_{j \leq i: x_j \le w} C[j, w-x_j] \end{align*} $$

Therefore, we can conclude that $C[n,w] = C[w]$.

$\endgroup$
2
$\begingroup$

This answer is wrong; see hengxin's.

The second is more efficient because it uses an (arbitrary) order of coins whereas the first one treats the set of denominations as unordered set.

You get from the first to the second by noting that you check different permutations of the same (multi-)set of coins, and then doing away with this redundancy.

$\endgroup$
  • $\begingroup$ Sorry to bother you with questions on this one-year-old answer. However, I don't quite understand why the second recurrence is more efficient given that the number of subproblems and dependencies among these subproblems are $nv$ and $2nv$ respectively, while they are $v$ and $nv$ respectively for the first recurrence. Secondly, what do you mean by "and then doing away with this redundancy"? Thanks. $\endgroup$ – hengxin Jun 10 '17 at 9:10
  • 1
    $\begingroup$ @hengxin Looking at this again, I think you're correct. The second recurrence seems to be an "unrolling" of the first, with negligible differences regarding cost (in abstract models; on real machines with caching and branch prediction, the second is maybe better?). I think you should add an answer! $\endgroup$ – Raphael Jun 10 '17 at 9:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.