Coins

​ 零钱兑换问题（Coin Change）有两个常见的变体：找到最小硬币数量和找到所有可能的组合。为了解决这两个问题，我们可以使用贪心算法、动态规划以及回溯搜索。请注意，贪心算法并不总是能找到全局最优解。

  1. 最小硬币数量：

a. 贪心算法：在特定条件下才能得到最优解，如美元和欧元等货币系统。从最大面值的硬币开始，尽可能多地使用当前面值的硬币。然后继续使用次大面值硬币。重复此过程直到达到目标金额或无法满足条件。

b. 动态规划：使用动态规划可以找到全局最优解。定义一个一维数组dp，其中dp[i]表示达到金额i所需的最少硬币数量。通过遍历所有可能的硬币面值，更新dp数组。最后，dp[target]就是最小硬币数量。

  1. 找到所有可能的组合：

a. 动态规划：使用动态规划可以找到所有可能的组合数。定义一个一维数组dp，其中dp[i]表示达到金额i的组合数。从第一个硬币开始，遍历所有可能的硬币面值，更新dp数组。最后，dp[target]就是所有可能的组合数。

b. 回溯搜索：使用回溯搜索可以找到所有可能的硬币组合。从最大面值的硬币开始，递归搜索所有可能的硬币组合。在递归过程中，当达到目标金额时，将当前组合添加到结果集中。当遍历完所有可能的组合时，返回结果集。

​ 动态规划解决最小硬币数量问题的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int coinChangeDP(int target, vector<int>& coins) {
    vector<int> dp(target + 1, target + 1);
    dp[0] = 0;

    for (int i = 0; i <= target; ++i) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[target] <= target ? dp[target] : -1;
}

int main() {
    vector<int> coins = {1, 4, 5};
    int target = 8;

    int minCoins = coinChangeDP(target, coins);
    cout << "Minimum number of coins: " << minCoins << endl;

    return 0;
}

​ 动态规划解决找到所有可能的组合数问题的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>

using namespace std;

int coinChangeCombinations(int target, vector<int>& coins) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;

    for (int coin : coins) {
        for (int i = coin; i <= target; ++i) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[target];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int target = 5;

    int combinations = coinChangeCombinations(target, coins);
    cout << "Total number of combinations: " << combinations << endl;

    return 0;
}

​ 回溯搜索解决找到所有可能的硬币组合问题的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(vector<int>& coins, int target, int start, vector<int>& current, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(current);
        return;
    }

    for (int i = start; i < coins.size(); ++i) {
        if (target - coins[i] >= 0) {
            current.push_back(coins[i]);
            backtrack(coins, target - coins[i], i, current, result);
            current.pop_back();
        }
    }
}

vector<vector<int>> coinChangeCombinationsBacktrack(int target, vector<int>& coins) {
    sort(coins.begin(), coins.end());
    vector<vector<int>> result;
    vector<int> current;
    backtrack(coins, target, 0, current, result);
    return result;
}

int main() {
    vector<int> coins = {1, 2, 5};
    int target = 5;

    vector<vector<int>> combinations = coinChangeCombinationsBacktrack(target, coins);
    cout << "Total number of combinations: " << combinations.size() << endl;

    for (const auto& combination : combinations) {
        for (int coin : combination) {
            cout << coin << " ";
        }
        cout << endl;
    }

    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用