第12次上机实验题目（找零钱）#

---

---

一、 利用贪心算法及动态规划算法求解“找零钱问题”#

问题描述#

设有n 种零钱，价值分别为v1=1, v2, … , vn, v1<v2<…<vn. 需要付的总钱数是Y. 问：如何付钱使所付零钱数最少?

输入格式#

输入零钱个数n，总钱数，各零钱价值

输出格式#

贪心算法及动态规划算法的零钱方案

样例输入#

4 28
1 5 14 18

样例输出#

28=18+5+5
28=14+14