贪心算法实战_当前最优选择可以解决

一 点睛

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。贪心算法正是“活在当下，看清眼前”的算法，从问题的初解开始，一步步做出当前最好的选择，逐步逼近问题的目标，尽可能得到最优解；即使得不到最优解，也可以得到最优解的近似解。

当然，贪心算法在解决问题的策略上看似“目光短浅”，只根据当前已有的信息做出选择，而且一旦做出选择，则不管将来有什么结果，都不会改变。换而言之，贪心算法并不是从整体最优来考虑的，它所做出的选择只是某种意义上的局部最优。对许多问题都可以使用贪心算法得到整体最优或整体最优的近似解。

二 贪心的本质

如果问题具有两个特性：贪心选择性质和最优子结构性质，就可以用贪心算法。

1 贪心选择性质

原问题的整体最优解可以通过一系列局部最优的选择得到。应用同一规则，将原问题变为一个相似的、但规模更小的子问题，而后的每一步都是当前最优选择。这种选择依赖于做出的选择，但不依赖于未做的选择。运用贪心算法解决的问题在程序的运行过程中无回溯过程。

2 最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

三 贪心算法求解步骤

1 贪心策略

确定贪心策略，选择当前看上去最好的一个。

比如挑选苹果，如果你认为个头最大的是最好的，那么策略就是选择当前最大苹果。

2 局部最优解

根据贪心策略，一步步得到局部最优解。

比如第1次选一个最大的苹果，记为a1，第2次从剩下的苹果中选择一个最大的苹果放起来，记为a2，以此类推。

3 全局最优解

把所有的局部最优解都合成原问题的一个最优解。

四 最优装载问题

1 问题描述

有一天，商人想买一批古董。虽然商船足够大，但承重为c，不能将所有的古董带上船，该怎么办？

2 问题分析

这是一个可以用贪心算法求解的最优装载问题，要求装载的物品尽可能多，而船的容量固定，那么优先选择重量小的物品，在容量固定的情况下，装的物品最多。可以采用重量最轻的先装船的贪心策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。

3 算法设计

a 先按照重量从小到大排序。

b 从小到大装船，直到装不下。

五 实现

1 代码

package GreedyAlgorithm;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class GreedyAlgorithm {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        list.add(4);
        list.add(10);
        list.add(7);
        list.add(11);
        list.add(3);
        list.add(5);
        list.add(14);
        list.add(2);
        Collections.sort(list);
        double weights = 0.0;
        int count = 0;
        double maxWights = 30;
        for (int i = 0; i < list.size(); i++) {
            weights += list.get(i);
            if (weights <= maxWights) {
                count++;
            } else {
                break;
            }
        }
        System.out.println(count);
    }
}

2 测试

5

六 算法分析

时间复杂度：由排序来决定，总时间复杂度为O(nlogn).

空间复杂度：在程序中使用了辅助变量 weights、count 等，空间复杂度为O(1)