,《完美的代价》需要用到意思呢私信小编01

写在前面

我最近无事可做。我正在为蓝桥杯（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)}”)