关键词：
贪心算法
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。
1.找零问题
假设商店老板需要找零n元钱，钱币的面额有：100元，50元，20元，5元，1元，如何找零是的所需钱币的数量最少？
t = [100, 50, 20, 5, 1] def change(t, n): m = [0 for i in range(len(t))] for i, money in enumerate(t): m[i] = n // money n = n % money return m, n print(change(t, 376))
2、背包问题
一个小偷在某个商店发现有n个商品，第i个商品价值vi元，重wi千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该该走那些商品？
0-1背包：对于一个商品，小偷要么把它完整拿走，要么留下。不能只拿走一部分，或则把一个商品拿走多次。
分数背包：对于一个商品，小偷可以拿走其中任意一部分。
举例： 商品1：v1=60 w1=10
商品2：v2=100 w2=20
商品3：v3=120 w3=30
背包容量量：W=50
goods = [(60, 10), (100, 20), (120, 30)] # 每个商品元组表示（价格，重量） goods.sort(key=lambda x: x[0] / x[1], reverse=True) def fractional_backpack(goods, w): m = [0 for i in range(len(goods))] total_v = 0 for i, (price, weight) in enumerate(goods): if w >= weight: m[i] = 1 total_v += price w -= weight else: m[i] = w / weight total_v += m[i] * price w = 0 break return total_v, m print(fractional_backpack(goods, 50))
3、拼接最大数字问题
有n个非负整数，将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大？
例例：32,94,128,1286,6,71可以拼接除的最?大整数为
94716321286128
li = [32, 94, 128, 1286, 6, 71] def number_join(li): li = list(map(str, li)) for i in range(len(li) - 1): for j in range(len(li) - i - 1): if li[j] + li[j + 1] < li[j + 1] + li[j]: li[j], li[j + 1] = li[j + 1], li[j] return "".join(li) print(number_join(li))
4、活动选择问题
假设有n个活动，这些活动要占?用同?一?片场地，?而场地在某时刻只能供?一个活动使?用。
每个活动都有?一个开始时间si和结束时间fi（题?目中时间以整数表示）,表示活动在[si, fi)区间占?用场地。
贪心讨论：最先结束的活动一定是最优解的一部分。
证明：假设a是所有活动中最先结束的活动，b是最优解重最先结束的活动
如果a=b，结论成?立。
如果a≠b，则b的结束时间?一定晚于a的结束时间，则此时?用a替换掉最优解中
的b，a?一定不不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)] # 保证活动时按照结束时间排好序的 activities.sort(key=lambda x: x[1]) def activity_selection(a): res = [a[0]] for i in range(1, len(a)): if a[i][0] >= res[-1][1]: # 当前活动的开始时间小于等于最后一个入选活动的结束时间 res.append(a[i]) return res print(activity_selection(activities))
动态规划
1、从斐波那契数列看动态规划
斐波那契数列列：Fn = Fn−1 + Fn−2
练习：使?用递归和?非递归的?方法来求解斐波那契数列列的第n项
# 子问题的重复计算 def fibnacci(n): if n > 0: if n == 1 or n == 2: return 1 else: return fibnacci(n-1) + fibnacci(n-2) # 动态规划（DP）的思想 = 递归式 + 重复子问题 def fibnacci_no_recurision(n): f = [0, 1, 1] if n > 2: for i in range(n-2): num = f[-1] + f[-2] f.append(num) return f[n]
4、钢条切割问题
某公司出售钢条，出售价格与钢条?长度之间的关系如下表：
问题：现有?一段?长度为n的钢条和上?面的价格表，求切割钢条?方案，使得总收益最?大。
钢条切割问题 --递推式
设?长度为n的钢条切割后最优收益值为rn，可以得出递推式：rn = max(pn,r1+rn-1,r2+rn-2,…,rn-1+r1),
第?个参数pn表示不不切割
其他n-1个参数分别表示另外n-1种不不同切割?方案，对方案i=1,2,...,n-1
将钢条切割为长度为i和n-i两段
方案i的收益为切割两段的最优收益之和
考察所有的i，选择其中收益最大的?案
钢条切割问题 --最优子结构
可以将求解规模为n的原问题，划分为规模更更小的子问题：完成?一次切割后，可以将产?生的两段钢条看成两个独?立的钢条切个问题。
组合两个子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大的，构成原问题的最优解。
钢条切割满足最优子结构：问题的最优解由相关?问题的最优解组合而成，这些子问题可以独立求解。
钢条切割问题 --自顶向下递归实现
def cut_rod_recurision_2(p, n): if n == 0: return 0 else: res = 0 for i in range(1, n+1): res = max(res, p[i] + cut_rod_recurision_2(p, n-i)) return res
## 实现复杂度O（2n） 2的n次方， 效率指数型增长，效率非常慢
钢条切割问题 --动态规划解法
递归算法由于重复求解相同子问题，效率极低
动态规划的思想:
1. 每个子问题之求解一次，保存求解结果
2. 之后需要此问题时，只需要查找保存的结果
def cut_rod_dp(p, n): r = [0] for i in range(1, n+1): res = 0 for j in range(1, i+1): res = max(res, p[j] + r[i - j]) r.append(res) return r[n]
## 时间复杂度为O（n的平方）
钢条切割问题 --重构解
如何修改动态规划算法，使其不不仅输出最优解，还输出最优切割?方案？
对于每个子问题，保存切割一次时左边切下的长度
def cut_rod_extend(p, n): r = [0] s = [0] for i in range(1, n+1): res_r = 0 # 价格的最大值 res_s = 0 # 价格最大值对应方案的左边不切割部分的长度 for j in range(1, i + 1): if p[j] + r[i - j] > res_r: res_r = p[j] + r[i - j] res_s = j r.append(res_r) s.append(res_s) return r[n], s
动态规划问题关键特征
- 最优子结构
- 原问题的最优解中涉及多少个子问题
- 在确定最优解使用哪些自问题时，需要考虑多少种选择
- 重叠子问题
5、最长公共子序列
一个序列的子序列是在该序列中删去若干元素后得 到的序列。
例：“ABCD”和“BDF”都是“ABCDEFG”的?序列
最长公共?子序列（LCS）问题：给定两个序列X和Y，求X和Y?度最?的公共?序列。
例：X="ABBCBDE" Y="DBBCDB" LCS(X,Y)="BBCD"
应?场景：字符串相似度?对
例如：要求a="ABCBDAB"与b="BDCABA"的LCS：
由于最后?位"B"≠"A"：
因此LCS(a,b)应该来源于LCS(a[:-1],b)与LCS(a,b[:-1])中更大的那?个
def lcs_length(x, y): m = len(x) n = len(y) c = [[0 for _ in range(n+1)] for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if x[i-1] == y[j-1]: # i j 位置上的字符匹配的时候，来自于左上方+1 c[i][j] = c[i-1][j-1] + 1 else: c[i][j] = max(c[i-1][j], c[i][j-1]) return c[m][n] def lcs(x, y): m = len(x) n = len(y) c = [[0 for _ in range(n + 1)] for _ in range(m + 1)] b = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # 1 左上方 2 上方 3 左方 for i in range(1, m+1): for j in range(1, n+1): if x[i-1] == y[j-1]: # i j 位置上的字符匹配的时候，来自于左上方+1 c[i][j] = c[i-1][j-1] + 1 b[i][j] = 1 elif c[i-1][j] > c[i][j-1]: # 来自于上方 c[i][j] = c[i-1][j] b[i][j] = 2 else: c[i][j] = c[i][j-1] b[i][j] = 3 return c[m][n], b def lcs_trackback(x, y): c, b = lcs(x, y) i = len(x) j = len(y) res = [] while i > 0 and j > 0: if b[i][j] == 1: # 来自左上方=>匹配 res.append(x[i-1]) i -= 1 j -= 1 elif b[i][j] == 2: # 来自于上方=>不匹配 i -= 1 else: # ==3 来自于左方=>不匹配 j -= 1 return "".join(reversed(res)) print(lcs_trackback("ABCBDAB", "BDCABA"))
算法竞赛进阶指南基本算法：递推与递归(代码片段)
递归实现指数型枚举题模板题：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<int,int>pii;#definepbpush_back#definefifirst#definesesecondconstintN=1e5+10;intn 查看详情
acwing进阶算法课level-4第七章基础算法(代码片段)
AcWing进阶算法课Level-4第七章基础算法启发式合并AcWing2154.梦幻布丁73人打卡AcWing3189.Lomsatgelral54人打卡manacher算法AcWing3188.manacher算法92人打卡最小表示法AcWing158.项链58人打卡构造AcWing516.神奇的幻方40人打卡AcWing2268.时态同步39人打卡... 查看详情
算法竞赛进阶指南基本算法-位运算(代码片段)
a^bPOJ1995位运算与快速幂关于快速幂的基本知识：每一个正整数都可以唯一的表示为若干指数不重复的2的次幂的和。（奇数由-1的偶数+1得到）b&1表示b的最低位（右边第一位）;b>>=1可以舍去最低位... 查看详情
算法竞赛进阶指南基础算法：前缀和与差分(代码片段)
激光炸弹题求一颗炸弹炸掉的最大价值，就是求以R为边长的正方形的覆盖范围的价值最大值。用二维前缀和把图跑一遍（构造），然后再跑一遍（遍历求R*R）；知道公式直接套用即可。#include<bits/stdc... 查看详情
算法进阶指南（dfs和bfs）---小猫爬山(代码片段)
题目链接：小猫爬山解法一：#include<iostream>#include<algorithm>usingnamespacestd;constintN=20;intn,m;intcat[N],sum[N];intans=N;voiddfs(intnow,intcnt) if(cnt>=ans)return;//剪枝 if(now==n+1) ans=min( 查看详情
《算法竞赛进阶指南》0x03差分(代码片段)
题目链接：https://www.acwing.com/problem/content/102/给定一个序列，只能对一个区间加一或者减一，问至少需要多少步使得所有数都变成一致的？有多少种一致序列？利用差分，对一个区间进行加一或者减一的话，一定是一个差分+1加上... 查看详情
算法进阶系列1空间搜索geohash算法(代码片段)
1.背景我们经常会用到App打车和共享单车，App界面上会显示出自己附近一个范围内可用的出租车或者共享单车：那如何发现以自己为圆心一定范围内的车呢？最直观的想法就是在数据库里存储每一辆车的经纬度，... 查看详情
算法竞赛入门码蹄集进阶塔335题(mt3330-3335）(代码片段)
算法竞赛入门【码蹄集进阶塔335题】(MT3330-3335）(文章目录)前言目录1.MT2330相似基因（1）题目描述基因片段由四个字母组成。下面给定两个基因片段，请返回它们的相似度。基因片段中每个字符前都有一个数字(不超过)，表示该... 查看详情
《算法竞赛进阶指南》0x32约数余数之和(代码片段)
题目链接：https://www.acwing.com/problem/content/201/求k对1-n所有数取模的和。证明一段可以作为等差数列来求，证明如下：（转自ACwing） 代码如下：#include<iostream>usingnamespacestd;typedeflonglo 查看详情
算法竞赛进阶指南usaco07tallestcow(代码片段)
前缀和，利用左右端点操作代替对区间的操作，从而优化输入，最后进行一次前缀和的操作，求得结果，这道题里面有个很关键的问题，就是需要去重，本来我想用set，但貌似有点鬼畜，算了，利用map去重，还有pair类型（学一... 查看详情
八数码的a*与ida*算法-搜索进阶练习1(代码片段)
八数码的A*与IDA*算法-搜索进阶练习1hdu1043：http://acm.hdu.edu.cn/showproblem.php?pid=1043poj1077：http://poj.org/problem?id=1077题意：众所周知的八数码问题，就不再描述了。不得不说，为了练习A*以及IDA*就直接看题解 查看详情
《算法竞赛进阶指南》0.6倍增(代码片段)
109.天才ACM给定一个整数M，对于任意一个整数集合S，定义“校验值”如下:从集合S中取出M对数(即2?M个数，不能重复使用集合中的数，如果S中的整数不够M对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大... 查看详情
算法竞赛入门码蹄集进阶塔335题(mt2326-2330）(代码片段)
算法竞赛入门【码蹄集进阶塔335题】(MT2326-2330）(文章目录)前言目录1.MT2326长度最小的连续子数组（1）题目描述给定一个含有n个非负整数的数组和一个正整数m。(1<n≤100000,1≤m≤1000000000)找出该数组中满足其和的长度最小的连... 查看详情
acwing进阶算法课level-4第六章搜索（模拟退火，爬山）(代码片段)
AcWing进阶算法课Level-4第六章搜索模拟退火AcWing3167.星星还是树110人打卡AcWing2424.保龄球78人打卡AcWing2680.均分数据72人打卡爬山法AcWing207.球形空间产生器51人打卡代码AcWing3167.星星还是树/*模拟退火功能：当一个问题的方案数量... 查看详情
动态规划算法-07背包问题进阶(代码片段)
简介我们在本专栏之前的文章介绍了基础的01背包问题及其解题思路，本文我们将讲述其拓展题型，也就是完全背包问题和多重背包问题。01背包问题首先，我们先来简单回顾一下经典的01背包问题，关于01背包的... 查看详情
算法竞赛进阶指南第二章--题解(代码片段)
就这样，我在繁忙的语言考试和期中考试还有科研中抽出时间来写完了这一章，感觉还有好多，但似乎看得到希望。HDOJ4699（对顶栈）题意：一个整数序列的编辑器有以下五种操作：1.Ix，在当前光标位置之后插入一个整数x，插... 查看详情
《算法竞赛进阶指南》0.4二分(代码片段)
102.最佳牛围栏农夫约翰的农场由N块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。... 查看详情
《算法竞赛进阶指南》0x43线段树扫描线算法poj2482(代码片段)
...每个点框定的区域，求区域叠加的最大值，可以通过如下算法：将每个可行点都标记，记录这些点上的权值，维护一个叶结点是一个权值点的线段树，更新的时候注意，由于所有的点都是可行点，所以右边界要在最后删除，遇到... 查看详情