题目描述
一家银行计划安装一台取款机。这台机器能够按要求的现金金额支付。这台机器使用了 $N$ 种不同面值的钞票,比如 $Dk ,\ k = 1,\cdots, N$,而且每种面值 $D_k$ 有 $nk$ 张钞票。例如,
$$N=3, \ n1 = 10,\ D1=100,\ n2=4,\ D2=50,\ n3=5,\ D3=10$$
意思是机器有 $10$ 张 $100$ 面值的钞票,$4$ 张 $50$ 面值的钞票,$5$ 张 $10$ 面值的钞票。
调用现金-机器应交付的所需现金量,并编写一个程序,计算小于或等于根据机器的可用钞票供应量可以有效交付的现金的最大现金量。
注:
@是机器交付货币的符号。例如,@可以代表美元、欧元、英镑等。
输入
程序输入来自标准输入。输入中的每个数据集代表一个特定的事务,其格式为:
cash N n1 D1 n2 D2 ... nN Dn
其中,$0 \leqslant cash \leqslant 100000$ 是请求的现金金额,$0 \leqslant N \leqslant 10$ 是票据面额的数量,$0 \leqslant nk \leqslant 1000$ 是 $Dk$ 面额的可用钞票数量,$1 \leqslant Dk \leqslant 1000$,$k = 1,\cdots,N$。输入的数字之间可以自由出现空格。输入数据正确。
输出
对于每一组数据,程序将结果打印到单独一行的标准输出。
样例
输入:
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
输出:
735
630
0
0
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla