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 $(S,F_{9})$ is a matroid with $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$.

$m_{ij}=$

		$j$
		0	1	2	3	4	5	6	7	8	9	10	11	12
$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 $v_{i}$ in the solution of the $(i,j)$-problem, then $m_{ij}$ = $m_{i+1,j}$
2. If we do use the coin with value $v_{i}$ in the solution of the $(i,j)$-problem, then $m_{ij}=1+m_{i,j-v_{i}}$

Therefore $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.