用Java 写一个贪婪算法
时间: 2024-05-16 07:15:41 浏览: 15
好的,这里给您提供一个用Java实现的贪婪算法,以解决背包问题为例:
```java
public class GreedyAlgorithm {
public static void main(String[] args) {
int[] weight = {2, 3, 4, 5, 9};
int[] value = {3, 4, 5, 8, 10};
int capacity = 20;
System.out.println("最大价值为:" + getMaximumValue(weight, value, capacity));
}
public static int getMaximumValue(int[] weight, int[] value, int capacity) {
int n = weight.length;
double[] unitValue = new double[n];
for (int i = 0; i < n; i++) {
unitValue[i] = (double) value[i] / weight[i];
}
double maxValue = 0;
while (capacity > 0) {
int maxIndex = -1;
for (int i = 0; i < n; i++) {
if (weight[i] <= capacity && (maxIndex == -1 || unitValue[i] > unitValue[maxIndex])) {
maxIndex = i;
}
}
if (maxIndex == -1) {
break;
}
maxValue += unitValue[maxIndex] * Math.min(capacity, weight[maxIndex]);
capacity -= weight[maxIndex];
}
return (int) maxValue;
}
}
```
这个算法的核心思想是,每次选择单位价值最高的物品放入背包中,直到背包无法再放入任何物品或者背包已经放满。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.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)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)