CSCE 411 Lecture 10

Lecture Slides

« previous | Monday, September 17, 2012 | next »

Matroid Formulation for Greedy Coin Change

Example denomination (1,2,4), value of 9.

We claim that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S,F_9)} is a matroid with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{ 1, 2, 4_1, 4_2, \}} and $F_{9}=\{\emptyset ,\{1\},\{2\},\{4_{1}\},\{4_{2}\},\{1,2\},\{1,4_{1}\},\{1,4_{2}\},\{2,4_{1}\},\{2,4_{2}\},\{1,2,4_{1}\},\{1,2,4_{2}\},\{1,4_{1},4_{2}\}\}$

The greedy algorithm sorts the coins according to values $4_{2}\leq 4_{1}\leq 2\leq 1$. The algorithm proceeds as follows:

1. $\{4_{2}\}\in F_{9}$
2. $\{4_{2},4_{1}\}\in F_{9}$
3. $\{4_{2},4_{1},2\}\not \in F_{9}$ (reject)
4. $\{4_{2},4_{1},1\}\in F_{9}$
5. return $\{4_{2},4_{1},1\}$

By the exchange property, at every intermediate step, there is always another action that can be taken until you reach the maximal state, which should be the optimal solution.

Dynamic Programming

Motivation: We have discussed a greedy algorithm for giving change. However, the greedy algorithm is not optimal for all denominations. Can we design an algorithm to give the optimal result for any denomination?

Dynamic approach: Vary the amount; restrict available coins.

Suppose we have coins with values $v_{1}>v_{2}>\dots >v_{n}=1$ to give a change amount $C$.

Let's call the $(i,j)$-problem the computation of the minimum number of coints with values $v_{i}>v_{i+1}>\dots >v_{n}=1$ for an amount $1\leq j\leq C$.

In this case, the original problem is the $(1,C)$-problem

Tabulation

Let $m_{ij}$ denote the solution to the $(i,j)$-problem. Thus, $m_{ij}$ denotes the minimum number of coins to make change for the amount $j$ using coins with values $v_{i},\ldots ,v_{n}$. It does not store the coin values—only the number of coins.

For example, denomination of $v_{1}=10$, $v_{2}=6$, and $v_{3}=1$.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_{ij} = }

		Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j}
		0	1	2	3	4	5	6	7	8	9	10	11	12
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i}	1	0	1	2	3	4	5	6	7	8	9	1	2	2
	2	0	1	2	3	4	5	1	2	3	4	5	6	2
	3	0	1	2	3	4	5	6	7	8	9	10	11	12

Note the following:

1. If we do not use the coin with value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} in the solution of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j)} -problem, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_{ij}} = Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_{i+1,j}}
2. If we do use the coin with value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} in the solution of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j)} -problem, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_{ij} = 1 + m_{i,j-v_i}}

Therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_{ij} = \begin{cases} m_{i+1,j} & v_i > j \\ \min\left(m_{i+1,j}, \ 1+m_{i,j-v_i} \right) & \mbox{otherwise} \end{cases}}

Algorithm

def dynamic_coin_change c, v, n
  m = Array.new(n, Array.new(c)) # allocate n x C matrix/array
  1.upto(c) {|i| m[n][i] = i}    # make change for amount i using coins of value v[n] = 1
  {{SOME LOOP} do |i,j|
    if v[i] > j then
      m[i][j] = m[i+1][j]
    else
      m[i][j] = [ m[i+1][j], 1+m[i][j-v[i]] ].min
    end
  end
  m[1][c]
end

Reconstructing the solution: When looking at the final number of coins, look where the answer came from and give value for that coin.