写在前面
我最近无事可做。我正在为蓝桥杯(Python)做准备。蓝桥杯主要考查算法问题。所以我也在网上找了一些资源来刷题。昨天,当我刷《完美的代价》的时候,在做这个问题的时候,卡住了。我想不通,甚至解决问题的代码。更可笑的是,昨晚睡觉的时候,就在想这个问题,结果没有用。不到一分钟,我就睡着了……
今天起床后在CSDN找思路。有博主提到《完美的代价》需要用到贪心算法,但是我没有认真学过相关算法,于是就去研究贪心算法,发现这个算法有意思吗?
私信小编01可以获得大量Python学习资料
什么是贪心算法
贪心算法不是具体的算法,而是一种算法的思想,或者解决问题的方法
要理解贪心算法,可以从这两个关键点入手:
贪心算法解决什么问题?
解决寻找最优解的问题。也就是说,这个问题的最终目的是得到一个最优解。比如从A地到B地的最短路径,100元可以买到商场里最多的东西等等。贪心算法是个什么样的想法?顾名思义,贪心算法是一种非常“贪心”的算法。其总体步骤可以概括为:将问题分解为多个子问题或多个步骤。在每个子问题或步骤中,执行一定的优化策略以获得局部最优解。得到每一步得到的所有优化。解,组合得到全局最优解,无需回溯处理
贪心算法最大的特点就是每一步都取最优解,不回溯。这样的策略执行起来自然更快,但是因为这种方法的短视。得到的解不是真正的全局最优解,但是贪心算法还是得到了一个近似最优解
0-1 背包问题
问题可以描述为:给定一组物品,每个物品都有自己的重量和价格,在有限的总重量内,我们如何选择使物品的总价格最高
通俗解释:如果你的背包只能装100个,里面放了一些重量和价值不一样的东西完全背包问题算法,怎么才能让你的背包价值最大化
这个问题的关键是,每一个转入背包的东西只能装进背包,不能装进背包,可以用0-1来表示。所以称为0-1背包问题。二是问题的两个局限。首先,背包的界限分明,只能承载这么多。二、事物的界限分明,你只有几样东西可以选择
因此,在这个问题中实际上有三种策略可供选择:
每次装的都是最高的颜值和重量比,也就是我们常说的性价比最高。每次加载时,它都在当前可用的项目中。, 最轻的
在三种策略中,策略一看起来最好
但是策略1的模糊化过大,需要根据特殊情况进行特殊修改
策略 2 和策略 3 是相同的,本身并没有太大的不同。只是观点不同
完美的价格
了解了贪心算法之后,我们再来看看这个算法问题。
问题描述
回文是一种特殊的字符串,从左到右的读法与从右到左的读法相同。小龙龙认为回文是完美的。现在给你一个字符串,不一定是回文,请计算最小交换次数完全背包问题算法,使字符串成为完美回文。
交换的定义是:交换相邻的两个字符
例如妈妈
第一个交换广告:mamda
第二次交换 md : madma
ma 的第三次交换:女士(回文!完美!)
输入格式
第一行是一个整数 N,表示后面的字符串的长度 (N 1: print(“Impossible”) return False else: return True
大家可以结合以上文字思路和代码片段来理解
然后就是计算步数
def get_step(n,s,sv,res): for i in range(n // 2): if s[i:].count(s[i]) != 1: temp = sv[:ni ].index(s[i]) # 是移动的步数 sv.pop(temp) res += temp s = sv[::-1] # 更新正序 else: # 字符数为1 ,直接移动到中间位置 res += n //2 -i #移动的步数 s[i] = None #下一步可以像偶数一样处理,相当于删除这个元素 sv = s[::-1 ] # 更新 sv 返回 res
这里的代码可以结合上图来理解
完整代码如下:
def Judge_hwen(n,s): # 判断是否可以形成回文 _str = set(“”.join(s)) if n % 2 == 0: # 对于长度为偶数的字符串 for i in _str : # 当字符个数不是偶数时,执行如下判断 if s.count(i) % 2 != 0: print(“Impossible”) return False else: return True else: # 对于字符串长度为奇数String temp = set() for i in _str: if s.count(i) % 2 != 0: temp.add(i) # 将奇数个字符放入 temp if len(temp) > 1 : print(“Impossible “) return False else: return Truedef get_step(n,s,sv,res): for i in range(n // 2): if s[i:].count(s[i ]) != 1 : temp = sv[:ni].index(s[i]) # 是移动的步数 sv.pop(temp) res += temp s = sv[::-1] # 更新正序列 else: #字符数为1,直接移动到中间位置 res += n //2 -i # 移动的步数 s[i] = None # 下一步可以看成偶数,相当于把这个元素删了 sv = s[::-1] # 更新sv return resn = int(input(“请输入字符串的长度:”))s = list(input(“请输入字符串:”))sv = s[:: -1]res = 0if Judge_hwen(n,s): print(f”所需的最小移动次数为:{get_step(n,s,sv,res)}”)所需的最小移动次数为:{get_step(n,s,sv,res)}”)所需的最小移动次数为:{get_step(n,s,sv,res)}”)
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 欧资源网