java贪心算法-蒲公英云

java贪心算法

迷南。 2021-06-10 20:38 594阅读 0赞

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。百度百科介绍传送门

举一个简单的例子
有一个背包，最多能承载150斤的重量，现在有7个物品，重量分别为[35, 30, 60, 50, 40, 10, 25]，它们的价值分别为[10, 40, 30, 50, 35, 40, 30]，如果是你的话，应该如何选择才能使得我们的背包背走最多价值的物品？

个人思路分析，也就是贪心算法的思路，通过求性价比，然后排序性价比，最后从性价比最大的开始选择，直到装满为止，这就是贪心算法的思路。下面上代码

/**
 * 贪心算法，我们可以通过求出性价比，然后排序性价比，然后从性价比最大的开始选择，直到装满为止。这就是贪心算法的思路。
 */
public class BeiBao {
    //定义最大负重，weight数组保存重量，values数组保存价值
    public int max_weight = 150;
    public static int[] weight = new int[] {35,30,60,50,40,10,25};
    public static int[] value = new int[] {10,40,30,50,35,40,30};
    //
    public void greedyPackage(int capacity, int[] weight , int[] value) {
        //性价比数组创建并排序
        int n = weight.length;//总个数
        double[] price = new double[n];//性价比数组
        int count[] = new int[n];//序号数组
        //求性价比
        for (int i = 0; i < n; i++) {
            price[i] = (double)value[i] / weight[i];
            System.out.println(price[i]);
            count[i] = i;
        }
        //性价比排序
        for (int i = 0; i < n - 1; i++) {
            for (int j = i; j < n - 1; j++) {
                if (price[j] < price[j + 1]) {
                    double tmp = price[j];
                    price[j] = price[j + 1];
                    price[j + 1] = tmp;
                    //交换性价比排序后，再吧序号交换,方便之后取数
                    int a = count[j];
                    count[j] = count[j + 1];
                    count[j + 1] = a;
                }
            }
        }
        //把质量和价值也按照性价比的排序顺序对应好，存到新数组里
        int newWeight[] = new int[n];
        int newValue[] = new int[n];
        for (int i = 0; i < n; i++) {
            newValue[i] = value[count[i]];
            newWeight[i] = weight[count[i]];
        }
        double maxValue = 0;
        //装东西，优先拿性价比高的
        for (int i = 0; i < n; i++) {
            if (capacity > newWeight[i]) {
                capacity -= newWeight[i];
                maxValue += newValue[i];
            }
        }
        System.out.print("共放下了" + (max_weight - capacity) +"kg重的东西\n");
        System.out.print("总价值" + maxValue);
    }
    public static void main(String[] args) {
        BeiBao greedyPackage = new BeiBao();
        greedyPackage.greedyPackage(greedyPackage.max_weight, weight, value);
    }
}

感谢大佬的高性能版

private void greedyPackageV2(Integer capacity, Integer[] weight , Integer[] value) {
        List<Integer> weightList = Arrays.asList(weight);
        List<Integer> valueList = Arrays.asList(value);
        Map<Integer,Double> price = new HashMap<>();//性价比数组
        List<Integer> count  = new ArrayList<>();
        for (int i = 0; i < weightList.size(); i++) {
            price.put(i, valueList.get(i) / weightList.get(i).doubleValue());
        }
         List<Map.Entry<Integer,Double>> list = new ArrayList<>(price.entrySet()); //将map的entryset放入list集合
        //根据性价比排序并取出倒序序后下标
        list.sort(Comparator.comparing(Map.Entry<Integer,Double>::getValue).reversed());//根据性价比倒序
        list.forEach(entry -> count.add(entry.getKey()));
         double maxValue = 0;
        //装东西，优先拿性价比高的
        for (int i = 0; i < count.size(); i++) {
            if (capacity > weight[count.get(i)]) {
                capacity -= weight[count.get(i)];
                maxValue += value[count.get(i)];
            }
        }
        System.out.println("总共放下了" +  (max_weight - capacity)  + "kg重的东西");
        System.out.print("总价值" + maxValue+"\n");
    }