找零钱最佳组合 假设商店货品价格(R)皆不大于100元（且为整数 ），若顾客付款在100元 内(P)，求找给顾客之最少货币个（张）数？ （货币面值50元(N50)，10元(N10)，5元 (N5)，1元(N1)四种），编写C语言或c++程序

为了找到找零钱的最佳组合，你可以使用动态规划的方法解决这个问题。我们可以创建一个二维数组 dp，其中 dp[i][j] 表示支付金额 i 时，最小需要的硬币张数，当最后一枚硬币是价值为 j 的货币（例如，dp[i][50] 表示支付 i 元，最后一枚是50元硬币的情况）。以下是 C++ 的基本算法：

#include <iostream>
using namespace std;

int coinChange(int R, int P, vector<int>& coins) {
    const int N = coins.size();
    vector<vector<int>> dp(P + 1, vector<int>(R + 1, -1));
    dp[0][0] = 0; // 零钱不需要硬币

    for (int i = 1; i <= P; ++i) {
        for (int j = 1; j <= R; ++j) {
            if (coins[N - 1] <= j && dp[i-coins[N-1]][j-coins[N-1]] != -1) {
                dp[i][j] = dp[i-coins[N-1]][j-coins[N-1]] + 1;
            }
            for (int k = 0; k < N - 1 && coins[k] <= j; ++k) {
                if (dp[i][j] == -1 || dp[i][j] > dp[i-coins[k]][j]) {
                    dp[i][j] = dp[i-coins[k]][j];
                }
            }
        }
    }

    return dp[P][R] != -1 ? dp[P][R] : -1; // 如果找不到合适的组合返回-1
}

int main() {
    vector<int> coins = {50, 10, 5, 1};
    int P = 87; // 顾客的付款金额
    cout << "最小硬币张数: " << coinChange(P, 100, coins) << endl;
    return 0;
}

这个程序会找出顾客支付 P 元时找零所需最少的硬币张数。如果无法组成有效的找零方案（如 P 大于所有硬币面值总和），函数将返回 -1。