贪心算法(贪婪算法)-慈云数据

贪心算法(贪婪算法)

文章目录

**贪心算法思想**
选择排序
平衡字符串
买卖股票的最佳时机
跳跃游戏
钱币找零
多机器调度问题
举办活动数量最多

无重叠区间

贪心算法思想

1.贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

2.贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。

3.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响。贪心算法对每个子问题的解决方案都做出选择，不能回退。

4.贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

5.实际上，贪心算法适用的情贪心算法(贪婪算法)况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。

该算法存在的问题

1.不能保证求得的最后解是最佳的

2.不能用来求最大值或最小值的问题

3.只能求满足某些约束条件的可行解的范围

选择排序

我们熟知的选择排序，其实采用的即为贪心策略。

它所采用的贪心策略即为每次从未排序的数据中选取最小值，并把最小值放在未排序数据的起始位置，直到未排序的数据为0，则结束排序。

import java.util.Arrays;
/**
 * 选择排序
 */
public class TestDemo {
    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void selectSort(int[] arr){
        //i: 未排序数据的起始位置
        for(int i = 0; i  
 
平衡字符串 
https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/ 
在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。 
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。 
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。 
返回可以通过分割得到的平衡字符串的 最大数量 。 
输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。 
解题思路: 不要有嵌套的平衡，只要达到平衡，就立即分割(贪心策略).我们假设 ‘R’ == 1, ‘L’ == -1 .只要累加等于 0 就算分割一次. 
 
class Solution {
    public int balancedStringSplit(String s) {
        int cnt = 0;
        int balance = 0;
        for(int i = 0; i  
买卖股票的最佳时机 
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。 
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 
返回 你能获得的 最大 利润 。 
 
class Solution {
    public int maxProfit(int[] prices) {
        int ret = 0;
        for(int i = 1; i  0)
                ret += curProfit;
        }
        return ret;
    }
}
 
跳跃游戏 
https://leetcode-cn.com/problems/jump-game/ 
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 
数组中的每个元素代表你在该位置可以跳跃的最大长度。 
判断你是否能够到达最后一个下标。 
贪心策略
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x + nums[x]，这个值大于等于 y，即 x+nums[x] ≥ y，那么位置y也可以到达。
这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置x，如果它在 最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以x+nums[x]更新 最远可以到达的位置。
在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回True作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。 
 
/**
 * 跳跃位置
 */
public class TestDemo3 {
    public class Solution {
        public boolean canJump(int[] nums) {
            int pos = nums.length - 1;
            int rightmost = 0;
            for (int i = 0; i 
                //如果可以到达当前位置，则更新最大
                if (i 
                    //每次更新最大的位置
                    rightmost = Math.max(rightmost, i + nums[i]);
                    //如果可以到达最后一个位置，则直接返回
                    if (rightmost = pos) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
}

    public static int solve(int money, int[][] moneyCount)
    {
        int num = 0;
        //首先选择最大面值的纸币
        for (int i = moneyCount.length - 1; i = 0; i--)
        {
            //需要的当前面值与面值数量取最小
            int c = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
            money = money - c * moneyCount[i][0];
            num += c;
        }
        if (money > 0)
            num = -1;
        return num;
    }
    public static void main(String[] args) {
        //存放纸币与数量: first:纸币，second:数量
        int[][] moneyCount = { { 1, 3 }, { 2, 1 }, { 5, 4 }, { 10, 3 }, { 20, 0 }
                ,{50, 1}, { 100, 10 } };
        Scanner scanner = new Scanner(System.in);
        int money;
        System.out.println("请输入要支付的钱");
        money = scanner.nextInt();
        int res = solve(money, moneyCount);
        if (res != -1)
            System.out.println(res);
        else
            System.out.println("No");
    }
}
 
多机器调度问题 
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间
输入:
第一行T（1
    public static int findMax(int[] machines){
        int ret = machines[0];
        for (int cur : machines)
        {
            if (ret