c++找零钱最佳组合

找零钱的最佳组合，取决于要找零的金额和可用的面额。以下是一个找零钱的最佳组合的例子：

假设我们要找零50元，可用的面额有1元、5元、10元和20元。为了找到最佳组合，我们可以遵循以下步骤：

1. 首先，我们可以尽量使用面额较大的钞票。因此，我们可以从最大面额的钞票开始找零，即20元。

2. 用尽可能多的20元钞票找零，直到不能再使用20元钞票为止。假设此时剩余的找零金额是10元。

3. 接下来，我们可以使用面额为10元的钞票来找零，直到不能再使用10元钞票为止。假设此时剩余的找零金额是5元。

4. 然后，我们可以使用面额为5元的钞票来找零，直到不能再使用5元钞票为止。假设此时剩余的找零金额是3元。

5. 最后，我们使用面额为1元的钞票来找零，直到找零金额为0为止。

根据上述步骤，找零50元的最佳组合可以是：两张20元钞票、一张10元钞票、一张5元钞票和三张1元钞票。

注意：最佳组合可能因可用的面额不同而有所变化，在实际情况中可能需要根据具体条件进行调整。

相关问题

找零钱最佳组合 假设商店货品价格(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。