贪心法找零钱Java
时间: 2024-05-26 16:09:33 浏览: 18
贪心法是一种常用的解决最优化问题的算法。在找零钱问题中,贪心法是一种可行的算法。具体实现如下:
1. 首先对硬币面值进行从大到小的排序。
2. 从面值最大的硬币开始,将其尽可能多地放入找零钱的集合中,直到无法再放入为止。
3. 接下来考虑面值次大的硬币,重复第2步,直到所有硬币都考虑完毕。
Java代码示例:
```java
public static int[] greedyChange(int[] coins, int money) {
Arrays.sort(coins);
int[] result = new int[coins.length];
for (int i = coins.length - 1; i >= 0; i--) {
result[i] = money / coins[i];
money = money % coins[i];
}
return result;
}
```
相关问题
贪心算法找零钱java
以下是Java实现贪心算法找零钱的代码:
```java
import java.util.Scanner;
public class GreedyAlgorithm {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请输入需要找零的钱数:");
int money = input.nextInt();
int[] coins = {25, 10, 5, 1}; // 硬币面值
int[] nums = new int[4]; // 硬币数量
for (int i = 0; i < coins.length; i++) {
nums[i] = money / coins[i];
money = money % coins[i];
}
System.out.println("需要的硬币数量分别为:");
for (int i = 0; i < coins.length; i++) {
System.out.println(coins[i] + "美分:" + nums[i] + "个");
}
}
}
```
运行结果:
```
请输入需要找零的钱数:33
需要的硬币数量分别为:
25美分:1个
10美分:0个
5美分:1个
1美分:3个
```
贪心算法找零钱java中档难度
以下是使用贪心算法实现找零钱问题的Java代码,时间复杂度为O(n):
```java
public static int[] change(int money) {
int[] coins = {25, 10, 5, 1};
int[] result = new int[4];
for (int i = 0; i < coins.length; i++) {
result[i] = money / coins[i];
money = money % coins[i];
}
return result;
}
```
该算法的思想是每次尽可能使用面值最大的硬币,直到找完为止。在这个问题中,由于硬币的面值是固定的,因此贪心算法是最优解。该算法的时间复杂度为O(n),其中n是硬币的种类数。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)