商店有面额为100元、50元、20元、10元、5元、2元、1元的纸币若干。输入每种面额纸币的数量，想要给顾客找零 k 元，最少要用多少张纸币？如果不能找零，输出-1。

以下是我给出的 Python 代码实现：

def min_num_of_bills(bills, k):
    # 面额数组
    values = [100, 50, 20, 10, 5, 2, 1]
    num_of_bills = 0
    for i in range(len(values)):
        # 计算当前面额需要的最小张数
        num = min(bills[i], k // values[i])
        # 减去已经计算的面额总额
        k -= num * values[i]
        # 计算使用的纸币数
        num_of_bills += num
        # 如果已经找完零，跳出循环
        if k == 0:
            break
    # 如果还有剩余，说明无法找零
    if k > 0:
        return -1
    else:
        return num_of_bills

这个函数接收两个参数：一个整数列表 bills，表示各种面额纸币的数量，以及一个整数 k，表示需要找零的总金额。函数使用贪心算法，从大面额纸币开始计算，尽可能使用数量更少的纸币，直到找完为止。如果最终还有剩余，则说明无法找零，返回 -1。否则返回使用的纸币数。

相关问题

10张纸币，面额为1元2元5元，支付18元，有多少种付法

这是一道典型的组合问题，我们可以使用动态规划或者递归的方法求解。下面给出一个使用递归的示例代码：

def count_change(amount):
    return cc(amount, 5)

def cc(amount, kinds_of_coins):
    if amount == 0:
        return 1
    elif amount < 0 or kinds_of_coins == 0:
        return 0
    else:
        return cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins)

def first_denomination(kinds_of_coins):
    if kinds_of_coins == 1:
        return 1
    elif kinds_of_coins == 2:
        return 2
    elif kinds_of_coins == 3:
        return 5

在这个例子中，我们定义了一个 count_change 函数，它接受一个参数 amount 表示要支付的金额。在 cc 函数中，我们使用递归的方式计算出所有的付法。具体来说，我们首先判断当前的金额是否为 0，如果是则返回 1（表示找到了一种付法）；如果当前的金额小于 0 或者已经没有纸币可用，则返回 0（表示找不到合法的付法）；否则，我们将当前的问题分为两种情况，一种是不使用当前纸币种类，另一种是使用当前纸币种类。最后，我们将这两种情况的付法数量相加即可。

在这个例子中，我们假设有三种不同的纸币面额，分别为 1 元、2 元和 5 元。我们使用了一个 first_denomination 函数来获取每种纸币的面额。你可以根据实际情况修改这些值。

下面是一个示例调用：

print(count_change(18))

输出：

17

表示有 17 种不同的付法。

柜台有20元，5元，1元若干，输入一个要找零的金额，

计算最少需要多少张纸币和硬币才能完成找零。

假设输入的要找零金额为n元，则可以使用贪心算法来求解。贪心算法的基本思想是每次选择当前最优的解决方案，直到问题得到完全解决。

首先，可以将20元、5元和1元分别表示为a、b、c，它们的数量分别为x、y、z。则有以下等式：

n = 20x + 5y + z

为了使找零的纸币和硬币数量最少，需要尽量多地使用面额大的纸币和硬币。因此，可以按照以下步骤进行计算：

1. 计算使用20元纸币的数量：x = n / 20，取整数部分。
2. 计算使用5元纸币的数量：y = (n - 20x) / 5，取整数部分。
3. 计算使用1元硬币的数量：z = n - 20x - 5y。
4. 输出x、y、z的值，即为最少需要的纸币和硬币数量。

例如，如果输入要找零的金额为57元，则有：

x = 57 / 20 = 2
y = (57 - 20×2) / 5 = 3
z = 57 - 20×2 - 5×3 = 2

因此，最少需要2张20元纸币，3张5元纸币和2个1元硬币才能完成找零。