Preparing NOJ

最少硬币问题

1000ms 65536K

Description:

设有n种不同面值的硬币,各硬币的面值存于数组T1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1:n]中。对任意钱数0m20001,设计一个用最少硬币找钱m的方法。

对于给定的1n10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m0m20001,编程计算找钱m的最少硬币数。

Input:

输入的第一行中只有1个整数给出n的值,2行起每行2个数,分别是T[j]Coins[j]。最后1 行是要找的钱数m

Output:

输出计算的最少硬币数,问题无解时输出-1。

Sample Input:

3
1 3
2 3
5 3
18

Sample Output:

5

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1221

Tags

Submitted 54

Passed 15

AC Rate 27.78%

Date 04/20/2019 10:03:10

Related

Nothing Yet