写一个贪心算法的java程序
时间: 2023-07-10 20:31:22 浏览: 47
下面是一个简单的贪心算法的Java程序,该程序用于求解背包问题。在这个问题中,有n个物品和一个背包。每个物品有一个重量和一个价值,背包有一个容量限制。要求选择一些物品,使得它们的总重量不超过背包容量,且总价值最大。
```java
import java.util.Arrays;
class Knapsack {
// 贪心算法求解背包问题
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] items = new int[n][2];
for (int i = 0; i < n; i++) {
items[i][0] = weights[i];
items[i][1] = values[i];
}
// 按照单位价值(即价值/重量)从大到小排序
Arrays.sort(items, (a, b) -> b[1] / b[0] - a[1] / a[0]);
int max = 0;
for (int i = 0; i < n; i++) {
if (capacity >= items[i][0]) {
max += items[i][1];
capacity -= items[i][0];
} else {
max += capacity * (items[i][1] / items[i][0]);
break;
}
}
return max;
}
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
int result = knapsack(weights, values, capacity);
System.out.println("最大价值为:" + result);
}
}
```
该程序实现了一个贪心算法,用于求解背包问题。它首先将物品按照单位价值(即价值/重量)从大到小排序,然后依次选择单位价值最大的物品放入背包中,直到背包容量达到上限或物品已经全部选择完毕。程序输出选择的物品的最大总价值。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)