贪心算法java实现

贪心算法是一种求解最优问题的算法，它在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到全局最优解。贪心算法通常可以用贪心选择性质来证明。在实现上，贪心算法一般使用循环和条件语句来实现。

下面是一个贪心算法求解背包问题的Java代码实现：

import java.util.Arrays;

public class Knapsack {
    public static void main(String[] args) {
        int[] weights = {10, 20, 30}; // 物品重量
        int[] values = {60, 100, 120}; // 物品价值
        int capacity = 50; // 背包容量
        double maxValue = knapsack(weights, values, capacity); // 求解最大价值
        System.out.println("最大价值为：" + maxValue);
    }

    public static double knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        double[] ratios = new double[n]; // 计算每个物品的性价比
        for (int i = 0; i < n; i++) {
            ratios[i] = (double) values[i] / weights[i];
        }
        double maxValue = 0;
        while (capacity > 0) { // 循环选择最优物品放入背包
            int index = getMaxRatioIndex(ratios);
            if (index == -1) {
                break;
            }
            if (weights[index] <= capacity) {
                maxValue += values[index];
                capacity -= weights[index];
            } else {
                maxValue += ratios[index] * capacity;
                capacity = 0;
            }
            ratios[index] = -1; // 标记已经选过的物品
        }
        return maxValue;
    }

    public static int getMaxRatioIndex(double[] ratios) { // 获取当前性价比最高的物品下标
        int index = -1;
        double maxRatio = 0;
        for (int i = 0; i < ratios.length; i++) {
            if (ratios[i] > maxRatio) {
                maxRatio = ratios[i];
                index = i;
            }
        }
        return index;
    }
}