2.背包问题-贪心算法-java
时间: 2024-05-11 09:10:21 浏览: 11
以下是使用Java实现背包问题的贪心算法的代码示例:
```java
import java.util.Arrays;
public class KnapsackProblem {
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
double maxValue = getMaxValue(weights, values, capacity);
System.out.println("The maximum value of items that can be carried is: " + maxValue);
}
public static double getMaxValue(int[] weights, int[] values, int capacity) {
int n = weights.length;
double[] valuePerWeight = new double[n];
for (int i = 0; i < n; i++) {
valuePerWeight[i] = (double) values[i] / weights[i];
}
Item[] items = new Item[n];
for (int i = 0; i < n; i++) {
items[i] = new Item(weights[i], values[i], valuePerWeight[i]);
}
Arrays.sort(items);
double maxValue = 0;
for (int i = n - 1; i >= 0; i--) {
if (capacity == 0) {
return maxValue;
}
int weight = Math.min(items[i].weight, capacity);
maxValue += weight * items[i].valuePerWeight;
capacity -= weight;
}
return maxValue;
}
static class Item implements Comparable<Item> {
int weight;
int value;
double valuePerWeight;
public Item(int weight, int value, double valuePerWeight) {
this.weight = weight;
this.value = value;
this.valuePerWeight = valuePerWeight;
}
@Override
public int compareTo(Item other) {
return Double.compare(valuePerWeight, other.valuePerWeight);
}
}
}
```