patternMinor
Two recurrences for the change-making problem with repetition
Viewed 0 times
problemtherecurrenceswithtwoforrepetitionmakingchange
Problem
The change-making problem with unbounded repetition is:
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?
- 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?
Solution
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]$.
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]$.
Context
StackExchange Computer Science Q#59618, answer score: 3
Revisions (0)
No revisions yet.