如何证明最优装载问题具有贪心选择性质

比如所你是按每次装入重量最小的作为贪心的选择，那么设重量从小到大（x1,x2,...,xn）是最优装载问题的一个最优解。设k=min{i|xi=1}.当k=1的时候（x1,x2,...,xn）是一个满足贪心性质的最优解。当k>1，令y=1，yk=0,yi=xi,i不等于k，那么yi与对应重量wi的乘积的和=w1-wk+wixi乘积的和，这个是小于等于本身wi*xi乘积的和的，小于容量c因此，（y1,y2,...,yn）也是最优装载问题的可行解。然而，xi的和与yi的和是相等的，也就是说，（y1,y2,...,yn）也是满组贪心性质的最优解。矛盾。

设某种货币系统为(1,5,10,25)四种币值(单位:元)，要用最少的币数找出 n元钱，
问:能否用贪心算法进行求解，并证明。(不要求写算法) 参考解答:贪心性质(最大面额优先选最多)证明:
对 n<=25的情况，易由穷举得证。
当 n>25时，设 n=1*a1+5*a2+10*a3+25*a4
为了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可将 5个 1元兑换为 1个 5元，币数减少。
a2<2，若 a2>=2，可将 2个 5元兑换为 1个 10元，币数减少。
当 a2=0时，a3<3，若 a3>=3，可将 3个 10元兑换为 1个 5元和 1个 25元，币数减 少。
当 a2>0时，a3<2，若 a2>=2，可将 1个 5元和 2个 10元兑换为 1个 25元，币数减 少。
即，为了使 a1+a2+a3+a4最小，所使用的 1、5、10元币的币数的上限为: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
则所使用的 1、5、10元币的币值上限为:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超过 25，因此，为了使 a1+a2+a3+a4最小，应使 a4达到最大。贪心选择性质得 证。
最优子结构性质证明:
当 a4的值确定后，为了使 a1+a2+a3+a4达到最小，须使 a1+a2+a3达到最小，仍为同 型的最优问题。