贪心算法实战

x33g5p2x  于2022-02-24 转载在 其他  
字(1.4k)|赞(0)|评价(0)|浏览(222)

一 点睛

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

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

二 贪心的本质

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

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)

相关文章