定理证明
- 格式：pdf
- 大小：72.44 KB
- 文档页数：2
引理 对每个正整数k，假设对所有的非负整数y有G k(y)=F k(y)，那么
G k+1(y)≤G k(y) ⇔F k+1(y)=G k+1(y)
证充分性. 如果F k+1(y)=G k+1(y)，由于F k+1(y)≤F k(y)，于是有
G k+1(y)=F k+1(y)≤F k(y)=G k(y)
必要性. 设G k+1(y) ≤G k(y)，由于F k+1(y)是最优解，因此有
F k+1(y) ≤
G k+1(y) ≤G k(y)
如果F k+1(y)中的x k+1=0，那么F k(y)=F k+1(y)，从而有
G k(y)=F k(y)=F k+1(y)≤G k+1(y)≤G k(y)
如果F k+1(y)中的x k+1≠0，令y’=y－v k+1x k+1，那么
F k+1(y’)=F k(y’) (+)
由此得到
G k(y’)=F k(y’)=F k+1(y’)≤G k+1(y’) ≤G k(y’)
⇒F k+1(y’)=G k+1(y’) (++)
将这个结果和y=y’+v k+1x k+1代入得到
G k+1(y)=G k+1(y’+v k+1x k+1)
=w k+1x k+1+G k+1(y’) =w k+1x k+1+F k+1(y’) (利用(++)公式)
= w k+1x k+1+F k(y’) (利用(+)公式)
= F k+1(y’+v k+1x k+1)=F k+1(y)
定理 对每个正整数k，假设对所有的非负整数y有G k(y)=F k(y). 令
v k+1=pv k－δ, 其中0≤δ<v k，p为正整数
则下面的命题等价：
(1) G k+1(y)=F k+1(y) 对一切正整数y
(2) G k+1(pv k)=F k+1(pv k)
(3) w k+1+G k(δ)≤pw k
证 (1)⇒(2). 令y=pv k即可.
(2)⇒(3). 使用k+1种硬币的重量至少不比使用k种硬币的重量更重，于是有
F k+1(y)≤F k(y)，而F k(y)=
G k(y)，因此
F k+1(y)≤
G k(y). (*)
令y=pv k，代入条件(2)和式(*)，有
G k+1(pv k) = F k+1(pv k) ≤G k(pv k)=pw k(**)
根据贪心法定义和v k+1=pv k－δ有
G k+1(pv k)=G k+1(v k+1+δ)=w k+1+G k(δ)
在上式中代入(**)式得条件(3)，即
w k+1+G k(δ)=G k+1(pv k)≤pw k
(3)⇒(1). 根据引理有G k+1(y)≤G k(y) ⇔F k+1(y)=G k+1(y). 使用反证法，我们只需证明：如果G k+1(y)>G k(y)，一定有w k+1+G k(δ)>pw k即可.
假设y*是使得G k+1(y)≤G k(y)不成立的最小正整数, 显然y*≥v k+1, 那么有
G k(y*)<G k+1(y*)=w k+1+G k+1(y*－v k+1)
上式两边加上G k(δ)得到
G k(δ)+G k(y*)<w k+1+G k(δ)+G k+1(y*－v k+1) (***)
因为已知贪心法对k种硬币得到最优解，于是
G k(y*+δ)≤G k(δ)+G k(y*) (****)
而
y*+δ=(v k+1+δ)+(y*－v k+1)=pv k+(y*－v k+1)
所以
G k(y*+δ)=G k[pv k+(y*－v k+1)]=pw k+G k(y*－v k+1) (*****)
将(****)和(***)代入上式得
pw k+G k(y*－v k+1)＝G k(y*+δ)≤G k(δ)+G k(y*)
<w k+1+G k(δ)+G k+1(y*－v k+1)
于是
pw k+G k(y*－v k+1)－G k+1(y*－v k+1) < w k+1+G k(δ)
因为y*是使G k+1(y)≤G k(y)不成立的最小正整数，于是G k+1(y*－v k+1)≤G k(y*－v k+1),从而得到
pw k < w k+1+G k(δ)。
