假设商店货品价格都不大于100元(且为整数) , 若顾客付款在100元内, 现有一个程序能在每位顾客付款后给出找零钱的最佳组合( 找给顾客货币张数最少)。假定此商店的货币面值只包括: 50元、 20元、10元、 5元、 2

元、1元。请问如何设计一个程序来实现这个功能？

首先，我们可以将所有的货币面值存入一个数组中，例如：

int[] coins = {50, 20, 10, 5, 2, 1};

然后，对于每一个顾客的付款金额，我们可以通过以下的贪心算法来计算最少的找零钱张数：

1. 初始化一个空的记录找零钱张数的数组 change。
2. 对于每一个货币面值 coin，循环执行以下步骤：
1. 计算当前面值 coin 可以找零的最大张数：maxCount = payment / coin。
2. 将 change 数组中对应面值 coin 的数量设为 maxCount。
3. 更新 payment 的值为 payment - maxCount * coin。
4. 如果 payment 的值已经为 0，说明已经找零完毕，退出循环。
3. 统计 change 数组中所有面值的数量之和，即为找零钱的最少张数。

下面是具体的 Java 代码实现：

public static int[] getChange(int payment) {
    int[] coins = {50, 20, 10, 5, 2, 1};
    int[] change = new int[coins.length];
    for (int i = 0; i < coins.length && payment > 0; i++) {
        int maxCount = payment / coins[i];
        change[i] = maxCount;
        payment -= maxCount * coins[i];
    }
    return change;
}

public static int getMinChangeCount(int payment) {
    int[] change = getChange(payment);
    int count = 0;
    for (int i = 0; i < change.length; i++) {
        count += change[i];
    }
    return count;
}

可以通过调用 `getChange` 方法来获取找零钱的组合，通过调用 `getMinChangeCount` 方法来获取最少的找零钱张数。例如：

int payment = 87;
int[] change = getChange(payment);
int count = getMinChangeCount(payment);
System.out.println("Payment: " + payment);
System.out.println("Change: " + Arrays.toString(change));
System.out.println("Min change count: " + count);

输出结果为：

Payment: 87
Change: [1, 1, 1, 0, 1, 0]
Min change count: 4

其中，change 数组表示找零钱的组合为 50 元1张、20 元1张、10 元1张、5 元0张、2 元1张、1 元0张；最少的找零钱张数为 4 张。