用Java编写一个贪心算法
时间: 2023-09-19 19:08:30 浏览: 43
以下是一个简单的 Java 贪心算法示例,用于找到能够组成给定目标金额的最少硬币数量:
```java
import java.util.Arrays;
public class GreedyAlgorithm {
public static void main(String[] args) {
int[] coins = {25, 10, 5, 1}; // 硬币面额
int target = 63; // 目标金额
int count = 0; // 硬币数量
Arrays.sort(coins); // 将硬币面额升序排序
for (int i = coins.length - 1; i >= 0; i--) { // 从大面额开始遍历
while (target >= coins[i]) { // 如果目标金额大于当前硬币面额
target -= coins[i]; // 扣除当前硬币面额
count++; // 硬币数量加一
}
}
System.out.println("最少硬币数量为:" + count); // 输出结果
}
}
```
该算法的思路是从大面额的硬币开始,每次尽可能地用当前面额的硬币去扣除目标金额,直到目标金额为零或无法再用当前面额的硬币扣除为止。该算法的时间复杂度为 O(n log n),其中 n 为硬币面额的数量。