原题：
在这个问题中，你需要读取一个整数值并将其分解为多张钞票的和，每种面值的钞票可以使用多张，并要求所用的钞票数量尽可能少。

请你输出读取值和钞票清单。

钞票的可能面值有 100,50,20,10,5,2,1。
——————————————————————————————————————————————————
算法是优先选最大的，先尽量用100，小于100部分再用50…
但优先选大真的对吗，直观上好像多选多的总数能少一点，但会不会出现大的数不够灵活，而小点的数恰恰正好的情况呢？
答案是，由于此题数据符合一定规律，优先选大的策略是正确的。
我们首先给出正确性证明，然后给出一种此贪心算法不适用的面额数据，最后给出检验一组面额数是否适用此贪心算法的一般方法。
正确性证明：
思路：分别考虑仅可以使用钞票1的情况，再考虑仅可以使用钞票1,2的情况，再考虑仅可以使用钞票1,2,5的情况..一直考虑到可以使用所有钞票的情况。考虑每种情况下钞票数最小的钞票组合，分别证明每种情况下，优先使用该情况下允许使用的面额大的钞票可以保证所有用的钞票总数量最少。
我们这样分别考虑不同情况可以把一个大问题分为多个阶段，而各个阶段的情况存在联系，存在规律，可以利用这个规律实现一般的证明。

初始情况我们允许只用1：则都为1 若面额数为11，则1,1,1,1,1,1,1,1,1,1,1（11个）
情况2（只用1,2）：每2个1可以凑齐一个2，肯定是2越多越好。我们尽量把1都合成2。 即2,2,2,2,2,1
注意，进行完上述操作，剩余的零星的1一定无法再合成2，因为如果凑够两个能够合成，我们就已经合成2了，它便不是剩余的1了
（这点看上去显然，但对证明有用）
情况3（只用1,2,5）：在情况2的基础上（情况2已经将数列变为了2，2,2,2,2，1）考虑
凑出5有两种方式 第一种，拆开一个2得到2个1，然后让这个1与另两个2合并，相当于2,2,2→1,5（1是拆完剩的）
第二组，利用零星的1，与2个2合并，相当于2,2,1→5
事实上我们允许所有的拆分和合成，比如把组合好的2拆成原来的1,1，比如2,2,1合成5.
当然，也允许1,1,1,1,1→5，但我们为了方便，尽可能少地去拆分已经组合好的2。
由于考虑如何拆分和合成的过程其实相当于考虑了所有可能的组合，因为所有的组合都能通过拆分和合成得到。
2,2,2→1,5与2,2,1→5都是钞票数减少的变化，故尽可能多的合成5后钞票数在当前情况下钞票数最少。
即5,5,1
情况4（只用1,2,5,10）与情况2类似，尽可能多地进行5,5→10的操作，直到5的个数不足。不必考虑零星的1,2也参与合成10的过程，因为这些零星的1,2加起来一定不到5。因为如果能到5，我们早就已经将它们合成为5了
即10,1.
情况5（只用1,2,5,10,20）与情况4类似，只需考虑10合成20
情况6（只用1,2，5,10,20,50）与情况3类似
情况7（只是用1,2,5,10,20,50,100）与情况2类似
证明完毕

另外，考虑一组不满足的面额，比如1,5,8合成10
并非8,1,1
而是5，5
套用上面的思路
初始：1,1,1,1,1,1,1,1,1,1
然后：5,5 1,1,1,1,1→5 5个1合成1个5，钞票数减少
再然后 考虑如何合成8
5→3,1,1
5,3→8（这俩5是不同的两个5，因为第一个5已经被拆了）
这俩相当于5,5→1,1,8（类似于化学反应式消去中间产物），如果企图再合成8，相当于钞票数增加

一般地，如何检验一组面额数是否满足优先选大的策略
就是基于上述思路，试图合成新加入的面额，合成新加入的面额时，要求一定尽量先使用次大面额，尽量不拆已经合成好的（比如原题中合成5时，我们用2,2,1 而不是把合成好的2拆成俩1，再用1,1,1,1,1）
迫不得已再分解更小一点的面额 比如三个2无法合成5，需要先拆1个，此时才可以拆
由于我们要求合成时优先选大的，故在必要的前置拆分之后（如果需要），合成方式唯一 比如合成5，就是2，2，1
考虑这种唯一的合成新加入面额的方式是钞票数减少的，不变的，还是增加的。若对于所有面额作为新加入面额的情况，合成新加入面额的方式始终为钞票数减少或者不变，则都可以用优先选大策略得到一组钞票数最少组合。在此基础上，若始终是“减少”，不存在“不变”的情况则优先选大策略得到的是唯一答案，否则可能唯一也可能不唯一，取决于待合成的面额具体数值和这组面额的具体数值。

比如这组面额为1,5,9
存在5,5→9,1
若总面额为10，则答案不唯一1,9或者5,5
若总面额为9，则答案唯一

想了很久，欢迎交流。