找零问题算法代码实现
时间: 2023-09-18 14:15:48 浏览: 39
找零问题是一个经典的贪心算法问题,通常用于计算如何给客户找零钱。以下是一个 Python 实现:
```python
def find_change(coins, amount):
coins.sort(reverse=True) # 将硬币按面值从大到小排序
change = []
for coin in coins:
while amount >= coin:
amount -= coin
change.append(coin)
if amount != 0:
return None # 找不到零钱
return change
```
其中,`coins` 是一组硬币的面值,`amount` 是需要找的零钱数。函数首先将硬币按面值从大到小排序,然后从最大的硬币开始遍历,如果当前硬币的面值小于等于剩余的零钱数,则将硬币加入找零列表中,并将剩余的零钱数减去当前硬币面值。如果剩余的零钱数为 0,则返回找零列表,否则返回 None,表示找不到零钱。
相关问题
算法,零钱找零问题,代码实现
零钱找零问题是一个经典的动态规划问题,也可以使用贪心算法来解决。下面给出两种解法的代码实现。
1. 动态规划解法:
```objc
#import <Foundation/Foundation.h>
NSInteger minCoins(NSArray<NSNumber *> *coins, NSInteger amount) {
NSMutableArray<NSNumber *> *dp = [NSMutableArray arrayWithCapacity:amount + 1];
for (NSInteger i = 0; i <= amount; i++) {
dp[i] = @(amount + 1);
}
dp[0] = @0;
for (NSInteger i = 1; i <= amount; i++) {
for (NSNumber *coin in coins) {
if (i >= coin.integerValue) {
dp[i] = @(MIN(dp[i].integerValue, dp[i - coin.integerValue].integerValue + 1));
}
}
}
return dp[amount].integerValue > amount ? -1 : dp[amount].integerValue;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray<NSNumber *> *coins = @[@1, @2, @5];
NSInteger amount = 11;
NSInteger result = minCoins(coins, amount);
NSLog(@"The fewest number of coins needed to make change for %ld is: %ld", amount, result);
}
return 0;
}
```
在上述代码中,我们定义了一个名为 `minCoins` 的函数来计算零钱找零问题的最少硬币数量。使用动态规划的思想,我们创建了一个数组 `dp`,其中 `dp[i]` 表示凑够金额 `i` 的最少硬币数量。通过迭代计算每个金额的最少硬币数量,最终得到凑够金额 `amount` 的最少硬币数量。
在 `main` 函数中,我们设定了硬币面额数组 `coins` 为 `[1, 2, 5]`,目标金额 `amount` 为 `11`,并调用 `minCoins` 函数来计算最少硬币数量。最后,使用 `NSLog` 打印出结果。
编译运行上述代码,将会输出:The fewest number of coins needed to make change for 11 is: 3,表示凑够金额 `11` 需要的最少硬币数量为 `3`。
2. 贪心算法解法:
```objc
#import <Foundation/Foundation.h>
NSInteger minCoins(NSArray<NSNumber *> *coins, NSInteger amount) {
NSInteger count = 0;
for (NSInteger i = coins.count - 1; i >= 0 && amount > 0; i--) {
if (coins[i].integerValue <= amount) {
NSInteger num = amount / coins[i].integerValue;
count += num;
amount -= num * coins[i].integerValue;
}
}
return amount == 0 ? count : -1;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray<NSNumber *> *coins = @[@1, @2, @5];
NSInteger amount = 11;
NSInteger result = minCoins(coins, amount);
NSLog(@"The fewest number of coins needed to make change for %ld is: %ld", amount, result);
}
return 0;
}
```
在上述代码中,我们同样定义了一个名为 `minCoins` 的函数来计算零钱找零问题的最少硬币数量。使用贪心算法的思想,我们从最大面额的硬币开始,尽可能多地使用该面额的硬币,然后逐步减小面额直到凑够目标金额。
在 `main` 函数中,我们同样设定了硬币面额数组 `coins` 为 `[1, 2, 5]`,目标金额 `amount` 为 `11`,并调用 `minCoins` 函数来计算最少硬币数量。最后,使用 `NSLog` 打印出结果。
编译运行上述代码,将会输出:The fewest number of coins needed to make change for 11 is: 3,表示凑够金额 `11` 需要的最少硬币数量为 `3`。
希望以上示例代码对你有所帮助。如果还有其他问题,请随时提问。
硬币找零问题贪心算法
好的,硬币找零问题是一个经典的贪心算法问题。假设我们有一些面值不同的硬币,现在需要找零 n 元钱,如何使用最少的硬币数找零?
贪心算法的思路是每次选择面值最大的硬币,直到找零金额为 0 或者无法再选择硬币为止。具体实现可以按照以下步骤:
1. 将硬币按照面值从大到小排序。
2. 从面值最大的硬币开始,尽可能多地选择该硬币,直到选择该硬币无法再凑出剩余的金额。
3. 重复步骤 2,直到找零金额为 0。
下面是 Python 代码实现:
```python
def coin_change(coins, amount):
coins.sort(reverse=True) # 按照面值从大到小排序
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
if amount == 0:
return count
else:
return -1
```
其中 coins 是硬币面值列表,amount 是需要找零的金额。如果无法凑出该金额,则返回 -1。