1.贪心理论与常见的证明方法-阿里云开发者社区

1.贪心理论与常见的证明方法

2024-01-10 36

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 1.贪心理论与常见的证明方法

贪心算法

贪心算法(Greedy Algorithm)是一种

(1)在每一步选择中都采取在当前状态下的最优决策(局部最优)

(2)并希望由此导致的最终结果也是全局最优的算法

贪心算法与一般的搜索，以及后面要讲的动态规划相比，不同之处在于:它不对整个状态空间进行遍历或计算，而是始终按照局部最优选择执行下去，不再回头。

因为这个特性，贪心算法不一定能得到正确的结果

除非可以证明，按照适当的方法做出局部最优选择,依然可以得到全局最优结果

能用贪心求解的题目，也都可以用搜索或动态规划求解，但贪心一般是最高效的

引入:零钱兑换问题

322.零钱兑换

https://leetcode.cn/problems/coin-change/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                if(coins[j]<=i)
                {
                    dp[i]=min(dp[i-coins[j]]+1,dp[i]);
                }
            }
        }
        dp[amount]=dp[amount]==INT_MAX-1?-1:dp[amount];
        return dp[amount];
    }
};

给一个硬币面额的可选集合coins,求拼成金额amount最少需要多少枚硬币。

例: coins = [20, 10, 5, 1], amount=46

答案: 46=20+20+5+ 1

零钱兑换:贪心

根据我们平时找钱的思路，一般我们会先考虑面值大的，零钱再用面值小的凑齐

“每次都选尽量大的面值”就是一个贪心思想

零钱兑换:贪心法的反例

零钱兑换:搜索

贪心算法的证明

由“零钱兑换"问题可以看出，贪心算法实际上是在状态空间中按局部最优策略找了一条路径。

贪心算法不一定能得出正确的解，在大部分题目上不能随便使用。

遇到题目，一般先想搜索、动态规划等基于全局的解法，若时间复杂度太高,再考虑贪心。

若要使用贪心算法，必须先证明其正确性。

除了反证法、数学归纳法等大家熟悉的方法外,我们再介绍几种常用的手法。

实战

860.柠檬水找零

https://leetcode.cn/problems/lemonade-change/description/

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        coins[5] = coins[10] = coins[20] = 0;
        for(int bill : bills) {
            coins[bill]++;
            if(!exchange(bill - 5)) return false;
        }
        return true;
    }
private:
    bool exchange(int amount) {
        for(int x : {20, 10, 5}) {
            while (amount >= x && coins[x] > 0) {
                amount -= x;
                coins[x]--;
            }
        }
        return amount == 0;
    }
    unordered_map<int, int> coins;
};

“零钱兑换"类问题在面值互相构成倍数时，贪心算法成立

在本题中，面值为[5, 10, 20]

如果能用1个10块找零,那用2个5块必然也也可以

也就是说，做出“用10块找零”这个决策,未来的可能性包含了” 用2个5块找零”以后未来的可

能性一决策包容性

所以本题可以贪心:优先使用面值较大的找零

455.分发饼干

https://leetcode.cn/problems/assign-cookies/description/

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int candy=0,child=0;
        while(child<g.size() && candy<s.size())
        {
            if(g[child]<=s[candy])
            {
                child++;
            }
            candy++;
        }
        return child;
    }
};

两种思路

一块饼干(尺寸s[j]) 发给谁?发给满足g[i] <= s[j]的最大g[i] (刚刚好能满足的孩子)

一个孩子(胃口g[i])吃哪块饼干?吃满足s[j] >= g[i]的最小s[j],不存在就别吃了

通俗点讲就是小饼干给小孩子，大饼干给大孩子,不能满足就不给了

决策包容性: -块饼干总是想要满足一一个孩子的,满足胃口更大的孩子,未来的可能性包含了满足

胃口更小孩子的可能性

把饼干和孩子排序,代码更容易实现

贪心算法的证明

决策范围扩展

在思考贪心算法时,有时候不容易直接证明局部最优决策的正确性

此时可以往后多扩展一一步, 有助于对当前的决策进行验证

实战

122.买卖股票的最佳时机II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++){
            ans += max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
};

这是一个预言家的炒股状态一知道未来每天的价格

当前持有股票，卖不卖?往后看一天，明天还涨那肯定不卖,明天跌那肯定卖啊!

当前没有股票，买不买?往后看一天,明天涨那肯定买,明天跌那肯定先不买!

最后就是完美结果一获得所有 prices[i]- prices[i- 1]> 0区间的收益

45.跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/

class Solution {
public:
    int jump(vector<int>& nums) {
        int now = 0;
        int ans = 0;
        while (now < nums.size() - 1) {
            int right = now + nums[now];
            if (right >= nums.size() - 1) return ans + 1;
            int nextRight = right;
            int next = now;
            for(int i = now + 1; i <= right; i++) {
                if(i + nums[i] > nextRight) {
                    nextRight = i + nums[i];
                    next = i;
                }
            }
            now = next;
            ans++;
        }
        return ans;
    }
};

看一下往后跳两步的所有可能性

贪心策略:若a能到b1, b2,b3,而b1, b2, b3能到的最远位置分别为C1, c2, c3,那应该从a

跳到c1, c2 ,c3中最大的一个对应的b。

Leetcode示意图

决策包容性:同样都是跳1步,从a跳到“能跳得更远”的b,未来的可达集合包含了跳到其他

b的可达集合，所以这个局部最优决策是正确的。

邻项交换

经常用于以某种顺序“排序”为贪心策略的证明

证明在任意局面下，任何局部的逆序改变都会造成整体结果变差

实战

1665.完成所有任务的最少初始能量

https://leetcode.cn/problems/minimum-initial-energy-to-finish-tasks/

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(),
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] - a[1] < b[0] - b[1];
            });
        int ans = 0;
        for(int i = tasks.size() - 1; i >= 0; i--) {
            ans = max(tasks[i][1], ans + tasks[i][0]);
        }
        return ans;
    }
};