贪心算法java硬币
时间: 2023-11-10 14:04:31 浏览: 50
好的,我知道了。对于贪心算法求硬币问题,我们可以先将硬币面值从大到小排序,然后从大到小依次选择硬币,直到凑出目标金额为止。以下是Java代码实现:
```java
public static int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return amount == 0 ? count : -1;
}
```
其中,coins为硬币面值数组,amount为目标金额。返回值为凑出目标金额所需的最少硬币数,如果无法凑出则返回-1。