同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2021_硬币兑换问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 54| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504248358600-Problem List-采集的数据-后羿采集器.html

Pro.ID

2021

Title

硬币兑换问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2021

AC

Submit

223

Ratio

34.98%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。

对任意钱数 m ，设计一个用最少硬币找钱m的方法。

对于给定的 1 ≤ n ≤ 10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0 ≤ m ≤ 20001，计算找钱m的最少硬币数。

输入

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

输出

Description

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。

对任意钱数 m ，设计一个用最少硬币找钱m的方法。

对于给定的 1 ≤ n ≤ 10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0 ≤ m ≤ 20001，计算找钱m的最少硬币数。

Input

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

Output

输出最少硬币数。问题无解时输出 -1 。

Sample Input

3
1 3
2 3
5 3
18

Sample Output

Author

John

样例输入