用java写一个贪心算法
时间: 2024-05-21 13:13:08 浏览: 5
好的,我可以回答这个问题。在Java中,贪心算法一般采用贪心策略来解决问题,即每次选择最优的解决方案,以期达到全局最优。一种经典的贪心算法是贪心背包问题,它将背包空间按价值从高到低排序,然后依次选取价值最高的物品放入背包中,直到背包装满或者所有物品都被放入为止。这种算法简单易懂,且可以快速得到近似最优解。
相关问题
用java 写一个贪心算法
下面是一个简单的 Java 实现贪心算法的示例:
假设有n个物品,每个物品有自己的价值和重量,现在有一个背包,它能承受的重量是m。我们将如何选择物品放入背包,使得背包中的总价值最大?
```
import java.util.Arrays;
public class GreedyAlgorithm {
/**
* 使用贪心算法解决0/1背包问题
*
* @param w 物品重量数组
* @param v 物品价值数组
* @param m 背包容量
* @return 最大价值
*/
public static int knapsack(int[] w, int[] v, int m) {
int n = w.length;
int[] index = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
// 按照单位重量的价值从大到小排序物品
Arrays.sort(index, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));
int maxValue = 0;
int currentWeight = 0;
for (int i = 0; i < n; i++) {
int itemIndex = index[i];
if (currentWeight + w[itemIndex] <= m) {
// 将物品放入背包中
currentWeight += w[itemIndex];
maxValue += v[itemIndex];
} else {
// 物品只能放一部分
int remaining = m - currentWeight;
maxValue += remaining * v[itemIndex] / w[itemIndex];
break;
}
}
return maxValue;
}
public static void main(String[] args) {
int[] w = {2, 3, 4, 5};
int[] v = {3, 4, 5, 6};
int m = 8;
int maxValue = knapsack(w, v, m);
System.out.println("最大价值:" + maxValue);
}
}
```
代码中的 knapsack 方法实现了使用贪心算法解决0/1背包问题的逻辑。它首先按照单位重量的价值从大到小排序物品,然后依次将物品放入背包中,直到背包装满或者所有物品都放完为止。如果无法放入整个物品,则只能放入一部分,贪心选择价值最高的部分放入背包中。最后返回背包中的最大价值。在 main 方法中,我们定义了一组简单的数据进行测试。
用Java写一个贪心算法
下面是一个 Java 实现的贪心算法示例,用于求解背包问题:
```java
import java.util.*;
public class GreedyAlgorithm {
public static void main(String[] args) {
int[] weights = {10, 20, 30};
int[] values = {60, 100, 120};
int capacity = 50;
int maxValue = getMaxValue(weights, values, capacity);
System.out.println("Max value: " + maxValue);
}
public static int getMaxValue(int[] weights, int[] values, int capacity) {
int n = weights.length;
Item[] items = new Item[n];
for (int i = 0; i < n; i++) {
items[i] = new Item(weights[i], values[i]);
}
Arrays.sort(items, Collections.reverseOrder());
int maxValue = 0;
for (int i = 0; i < n; i++) {
int w = items[i].weight;
int v = items[i].value;
if (capacity >= w) {
capacity -= w;
maxValue += v;
} else {
double fraction = (double) capacity / (double) w;
maxValue += fraction * v;
break;
}
}
return maxValue;
}
static class Item implements Comparable<Item> {
int weight;
int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
@Override
public int compareTo(Item other) {
double ratio = (double) value / (double) weight;
double otherRatio = (double) other.value / (double) other.weight;
return Double.compare(ratio, otherRatio);
}
}
}
```
在这个示例中,我们使用贪心策略来解决背包问题。我们首先将物品按照单位价值从高到低进行排序,然后依次选择物品,直到背包的容量不足以装下下一个物品为止。如果当前物品可以完全装入背包中,则将其全部装入;否则,我们将只装入一部分物品,使得背包装满。最后,我们返回所有选中物品的总价值。
在这个示例中,我们使用了一个内部类 Item 来表示物品,它包含两个属性:weight 和 value。我们还实现了 Comparable 接口,并重写了 compareTo 方法,以便在排序时按照单位价值从高到低进行排序。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)