题目 1483: A2.1 完全背包问题之硬币找零(贪心算法求解)

 时间限制: 3s 内存限制: 256MB

题目描述

给定n种硬币，第i种硬币的面值为coins[i-1]，目标金额为amt，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回−1；

默认输入的硬币面值coins有10个(空格分割，未排序)，第11个输入为目标金额amt，例如输入

8 5 6 2 20 50 10 4 1 9 247

硬币面值分别为8 5 6 2 20 50 10 4 1 9，目标金额247；

贪心找零结果为 50*4 + 20*2 + 6*1 + 1*1，共计8个硬币

输入格式

8 5 6 2 20 50 10 4 1 9 247

输出格式

8

样例输入

无

样例输出

无

提示

无