分享
贪心算法之Python算法题实战 -《完美的代价》
输入“/”快速插入内容
贪心算法
之Python算法题实战 -《完美的代价》
用户102
用户102
2023年10月28日修改
⏳
Written 03-21-2021
写在前面
最近也没什么事可做,就在备赛蓝桥杯(Python).蓝桥杯主要考察的是算法题目.所以我也在网上找了些资源刷题,昨天当我刷到《完美的代价》这道题目的时候,我就被卡住了.怎么想也想不通,就连解题代码也看不懂.更搞笑的是,昨天晚上我睡觉的时候,就在思考这道题目,结果不到五分钟,我就入睡了...
今天起床后,我就在CSDN里面找寻思路,有些博主提到,《完美的代价》需要用到
贪心算法
,但是我也没正经学过相关的算法,所以就去研究了一下贪心算法,发现这个算法还有点意思呢😂
What is
贪心算法
贪心算法
并不是一个具体的算法,而是一种算法的思想,或者说是解决问题的一种思路
要想弄明白
贪心算法
,可以从这两个关键点入手:
1.
贪心算法
解决什么问题
解决求最优解问题。即此问题的最终的目的,是为了得到一个最优解。比如,从A地到B地之间的最短路径,100块钱可以在一个商场里买到的东西最多,等等之类的
2.
贪心算法
是怎样的一种思路
顾名思义,
贪心算法
,是一种很“贪”的算法。它的整体步骤,可以归纳为:
将问题分解成多个小问题或者多个步骤
在每个小问题或者步骤中,执行某种
最优化
策略,得到局部最优解
所有每个步骤得到的最优化解,组合得到全局最优化解,不做回溯处理
💡
贪心算法
最大的特点,就是在每一步中取
最优化
的解,不会回溯处理。这样的策略,自然在执行速度上更快,但是因为这种方法的短视。会导致得的解并不是真正的全局最优解,但是贪心算法得到的依然是一个近似最优解
0-1背包问题
问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高
通俗解释:假如你有一个只能承重100的背包,你往里面装一些重量和价值不等的东西,怎样才可以让你的背包中的价值最大
这个问题中就是关键在于,每个转入背包的东西,只能是被装入背包和不被装入背包两种状态,可以用0-1表示。所以叫0-1背包问题。其二,就是这个问题的两个限定。第一,背包的边界是明确,它只能承重那么多东西。第二,东西的边界是明确的,你只有那么一些东西可以选择
故而,这个问题其实有三种策略可以选择:
1. 每次装入的都是价值和重量比率最高的,也就是我们常说的性价比最高的
2. 每次装入的是当前可选择的东西中,价值最高的
3. 每次装入的是当前可选择东西中,重量最轻的
这三种策略中,策略一看起来最好的策略
但是,策略一的模糊化太大,需要根据特殊的情况,做出特殊的改变
策略二和策略三相同,本身上并没有太多不同。只是二者的视角不同