A Polynomial-time Algorithm for the Change-Making Problem

David Pearson, A Polynomial-time Algorithm for the Change-Making Problem, Technical Report TR 94-1433, 1994.

コインの両替問題のインスタンス $c_{1},c_{2},\cdots,c_{n}$ について，貪欲法が常に最適解を返すかどうかを $O(n^{3})$ で判定する．更に，答えが"NO"の場合は，最適解と貪欲解が一致しない最小の反例を求めることができる．

色々な定義

仮定

n枚のコインの額面を正整数 $c_{1}>c_{2}>\cdots>c_{n}$ とする．更に， $c_{n}=1$ と仮定する（そうでなければ1を表現できない）．

ベクトルによる表現

$C=[c_{1},c_{2},\cdots,c_{n}]$ とする．
$x$ を表す各コインの枚数を $V=[v_{1},v_{2},\cdots,v_{n}]$ とすると，
$x=V \cdot C$ が成り立つ．

辞書式順序・包含関係

ベクトル $U=[u_{1},u_{2},\cdots,u_{n}]$ と $V=[v_{1},v_{2},\cdots,v_{n}]$
に対して，辞書式順を以下で定義．
[tex:U

貪欲表現・極小表現

$x$ の貪欲表現を以下で定義．
$G(x)$ ： $x=V \cdot C$ となる $V$ の中で辞書式順最大のもの

$x$ の極小表現を以下で定義．
$M(x)$ ： $x=V \cdot C$ となる $V$ の中で $|V|$ が最小であるものの内，辞書式順最大のもの

$U$ が貪欲 $\Leftrightarrow U = G(U \cdot C)$
$U$ が極小 $\Leftrightarrow U = M(U \cdot C)$

コインシステムが正統

コインシステムが正統 $\Leftrightarrow \forall x \; G(x)=M(x)$

補題1

(a) $U \subseteq V$ かつ $V$ が貪欲 $\Rightarrow U$ が貪欲
(b) $U \subseteq V$ かつ $V$ が極小 $\Rightarrow U$ が極小
証明は論文参照．

最小の反例の性質

$C$ が正統でないとする． $w$ を $G(w) \neq M(w)$ となる最小の反例とする．

以下，
$G(w)=[g_{1},g_{2},\cdots,g_{n}]$
$M(w)=[m_{1},m_{2},\cdots,m_{n}]$
とする．

この時， $G(w)$ と $M(w)$ の非ゼロのインデックス集合は互いに素．言い換えると， $g_{k} \neq 0, m_{k} \neq 0$ となる $k$ は存在しない．これは，補題1と $w$ の最小性から背理法で証明可能．

$i$ ： $M(w)$ の最初の非ゼロのインデックス
$j$ ： $M(w)$ の最後の非ゼロのインデックス
とすると，以下の定理が成立する．

定理1

$M(w)$ は以下で構成できる．
$m_{1},\cdots,m_{j-1}$ ： $G(c_{i-1}-1)$ に一致
$m_{j}$ ： $G(c_{i-1}-1)$ の対応する要素より1大きい
$m_{j+1},\cdots,m_{n}$ ：0
証明は論文参照．

$w$ の候補は考えられる $i,j$ について全パターン（ $O(n^{2})$ 通り）試せばよい．従って，以下のようにして $w$ と $M(w)$ を求めることが出来る．

Step.0

$w \leftarrow \infty$
$M(w) \leftarrow []$
と初期化．

Step.1

iを2からnまで変化させる．

Step.2

jをiからnまで変化させる．

Step.3

$G(c_{i-1}-1)$ を求める．
$M(w')$ を構成する．
$w'$ を求める．
$G(w')$ を求める．
$|M(w')|<|G(w')|$ かつ[tex:w'

Step.4

iとjについて繰り返し．

適用可能な問題

AOJ 2069 Greedy, Greedy.
＜2012/07/29追記＞
Codeforces 10E Greedy Change（[twitter:@iwiwi]さんに教えてもらいました．Thanks!!）

＜追記ここまで＞

Javaによるサンプル

void checkCanonical(int[] c){
	int n=c.length;
	sort(c);
	for(int i=0; i<n/2; i++){
		int t=c[i];
		c[i]=c[n-1-i];
		c[n-1-i]=t;
	}
	int minW=-1;
	int[] minMw=null;
	for(int i=1; i<n; i++){
		int x=c[i-1]-1;
		int[] gi=new int[n];
		for(int k=0; k<n; k++){
			gi[k]=x/c[k];
			x%=c[k];
		}
		for(int j=i; j<n; j++){
			int[] mw=new int[n];
			int mwSum=0;
			int w=0;
			for(int k=0; k<n; k++){
				if(k<j)
					mw[k]=gi[k];
				else if(k==j)
					mw[k]=gi[k]+1;
				else
					mw[k]=0;
				w+=mw[k]*c[k];
				mwSum+=mw[k];
			}
			int[] gw=new int[n];
			int gwSum=0;
			int t=w;
			for(int k=0; k<n; k++){
				gw[k]=t/c[k];
				t%=c[k];
				gwSum+=gw[k];
			}
			if(mwSum<gwSum&&(minW==-1||w<minW)){
				minW=w;
				minMw=mw.clone();
			}
		}
	}
	// minW==-1ならcは正統
	// そうでないなら，minWが最小の反例，minMwはminWの極小表現
}

戯言

面白いと思ったのが，特定の $x$ について貪欲解が最適解かどうかを判定する問題がNP-hardであるにも関わらず，任意の $x$ について成立するかを判定する問題がPに属するという事．定理1の証明が中々トリッキーで思いつかないなあと思った．実質4pageしかないので，読むのが楽だった．