个人主页网站制作,网站seo快速优化,cantos wordpress,wordpress 字体代码文章目录 买卖股票的最佳时机问题穷举解法贪心解法 物流站的选址#xff08;一#xff09;穷举算法贪心算法 物流站的选址#xff08;二#xff09;回合制游戏快速包装 买卖股票的最佳时机问题 给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。如果你… 文章目录 买卖股票的最佳时机问题穷举解法贪心解法 物流站的选址一穷举算法贪心算法 物流站的选址二回合制游戏快速包装 买卖股票的最佳时机问题 给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易即买入和卖出一支股票设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入 : [7, 1, 5, 3, 6, 4] 输出 : 5 解释 : 在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出 最大利润 6 - 1 5 。 注意利润不能是 7 - 1 6, 因为卖出价格需要大于买入价格。 示例 2 : 输入 : [7, 6, 4, 3, 1] 输出 : 0
穷举解法 对所有可能的买入和卖出时机进行遍历并记录最大差值。
prices [7, 1, 5, 3, 6, 4]
def find_max(prices):if len(prices) 2:return 长度不够max_profit 0for i in range(len(prices)):for j in range(i1,len(prices)):if (prices[j]-prices[i])max_profit:max_profitprices[j]-prices[i]return max_profit
print(find_max(prices))贪心解法 最贪心的投资方案显然是在低价时买人高价时卖出。是找到一个波峰和一个波谷且波峰在波谷之后出现使波峰和波谷在竖功方向上的差别最大这样一来在波谷处买人在波峰处卖出赚取的差价最大。 假设我们要在第i天卖出那么就要在前-1天中的某一天买人贪心地考虑当我们在前i-1天中以最低价买人时赚的钱最多这正是当前最好的方案。所以可以只遍历卖出的时间买入的价格就是卖出前的最低价。与“暴力的穷举算法相比这样的贪心算法把时间复杂度从0n*2)了降低到了0(n)。
prices [7, 1, 5, 3, 6, 4]
def find_max(prices):if len(prices) 2:return 长度不够max_profit 0min_priceprices[0]for i in range(len(prices)):if prices[i]-min_pricemax_profit:max_profitprices[i]-min_priceif prices[i]min_price:min_priceprices[i]#维护一个最小值return max_profit
print(find_max(prices))物流站的选址一 小余的家乡共有n个地方可以建设物流站。每一个物流站都只能对附近直线距离为ai的区域包括边界中的居民点进行配送另外小余的家乡有m个居民点需要提供物流配送服务。 小余作为一个关心家乡的老板既要满足所有居民的需求即每个居民点至少有一个可以提供服务的物流站又要保障公司的利益即建立较少的物流站小余必须担任物流站选址规划的重任要计算最小需要建设多少物流站才能服务到每一个居民点。 为了简化问题物流站和居民点都可以看作二维平面上的点物流站和居民点之间的距离就是两点之间的直线距离。
数据 n4,表示物流站选址的个数。m9附近居民点的个数。 接下来表示每个物流站选址的坐标和配送范围 2,1,2;-3,0,3;-1,0,2;2,-1,3。 每个居民点的坐标 1,2-4,1-1,11,1-2,02,03,0-1,-1-3,-2。
穷举算法 一共有4个地址每个地址要么被选择作为物流站要么否。一共只有16种方案可穷举。用二进制表示方案
import numpy as np
import math
n4#物流站地址个数
m9#居民点个数
X[2,-3,-1,2] #物流站地址横坐标
Y[1,0,0,-1]#物流站地址纵坐标
a[2,3,2,3]#物流站地址配送距离
u[1,-4,-1,1,-2,2,3,-1,-3]#居民点横坐标
v[2,1,1,1,0,0,0,-1,-2]#居民点纵坐标flag[False for i in range(m)] #标记每个居民点是否被覆盖
#判断物流站i能否服务居民点j
def can_serve(i,j):return (X[i]-u[j])*((X[i]-u[j]))(Y[i]-v[j])*(Y[i]-v[j])a[i]*a[i]max_snp.power(2,n)#总方案数 2的n次方 用二进制表示方案[0,0,0,0]0 [0,0,0,1]1,1表示可选def ten_two(max_s,num):将num转换为二进制:param max_s: 方案总数:param num: 当前方案代码 且nummax_s:return:result [0 for i in range(int(math.log(max_s,2)))] #二进制初始化num_two bin(num) # 将num转换为二进制 如5结果为0b101num_two str(num_two[2:]) # 去除0b 格式为字符geshu int(len(result)) - int(len(num_two))result1 [0 for i in range(geshu)]result1.extend([int(i) for i in num_two])return result1def solve():ansn#初始化结果为nbests0 #最优方案for s in range(max_s):#遍历每个方案station0 #当前方案的物流站个数for j in range(m):#遍历每个居民点flag[j]Falsetempten_two(max_s,s) #当前方案二进制for i in range(len(temp)): # 遍历每个方案选址if temp[i]1:station 1# 将物流站i服务范围内的每个居民点打上标志for j1 in range(m):if can_serve(i,j1):flag[j1]True# 判断当前方案能否覆盖每个居名点并更新答案num 0for j2 in range(m):if flag[j2]:num 1if num m:if stationans:ansstationbestssreturn ans,ten_two(max_s,bests) # 最优选址个数,最优选址方案ans,bestsolve()
print(最优选址个数:,ans)
print(最优选址方案:,best)贪心算法 既然要覆盖每一个居民点那么每次都要尽可能多地覆盖几个居民点这正是贪心算法的核心思想。 步骤如下 1选一个包含最多未覆盖的居民点的物流站站址在此处新建物流站。 2重复步骤1直到所有居民点都被覆盖。 贪心算法在这个样例中恰好得到了最优解但正如前面提到的根本不存在解决这个问题的快速解法贪心算法计算出的结果不一定是最优解但这个解不会太差。
n4#物流站地址个数
m9#居民点个数
X[2,-3,-1,2] #物流站地址横坐标
Y[1,0,0,-1]#物流站地址纵坐标
a[2,3,2,3]#物流站地址配送距离
u[1,-4,-1,1,-2,2,3,-1,-3]#居民点横坐标
v[2,1,1,1,0,0,0,-1,-2]#居民点纵坐标flag[False for i in range(m)] #标记每个居民点是否被覆盖
#判断物流站i能否服务居民点j
def can_serve(i,j):return (X[i]-u[j])*((X[i]-u[j]))(Y[i]-v[j])*(Y[i]-v[j])a[i]*a[i]new_num[0 for i in range(n)]#每个选址覆盖的居民点数初始化为0best[0 for i in range(n)] #初始化最优选址
def solve():num0 #当前覆盖的居民点个数station0#需要建造的物流站个数while(numm):#遍历每一个居民#选一个包含最多未被覆盖的居名点的物流站将它作为一个修建点new_station0for i in range(n):#遍历每一个选址new_num[i]0#i选址覆盖的居民点数初始化为0for j in range(m):#遍历每一个居民点if flag[j]False and can_serve(i,j):new_num[i]1if new_num[i]new_num[new_station]:new_stationibest[new_station]1 #当前的选址索引#在该处新建物流站更新相关变量for j in range(m):##遍历每一个居民点if flag[j]False and can_serve(new_station,j):flag[j]Truenum1station1return station,best #个数 、方案
station,bestsolve()
print(最优选址个数,station)
print(最优方案,best)物流站的选址二 小算为了扩大物流运输服务的范围打算开辟一条新的物流运输线路这条线路可以认为是数轴上长度为L的线段在坐标0,1,工上有L1个居民点需要在其中若干个居民点建设物流站每一个物流站都只能对线路上直线距离a以内的区域(含边界)提供服务。这条物流运输线路很长并非每个居民点都可以建设物流站但为了满足长距离运输的需求线路上每一个居民点都必须在服务范围内现在小算需要重新考虑物流站选址的问题如图所示。 数据格式 n4,表示物流站选址的个数 L8表示物流运输线路的长度 接下来的n行每行有2个整数Xi,ai。表示第i个物流站选址的坐标和服务距离 4,3 1,1 6,2 2,2 以样例为例如果按照前一个问题中的贪心的思路每次尽可能增加服务范围结果如图。 但是最优解显然不需要三个物流站两个就够了。 这个例子再次说明了用贪心算法的思想解决问题时只考虑眼前利益并不一定能得到最优解。现在换一种贪心算法的思路从最左侧开始每次在左侧尽可能增加服务范围这样的思路恰好得到了最优解。同样是贪心算法为什么这个思路就可以得到最优解呢?下面来分析原因。 首先要注意的是物流站的选址规划与顺序无关所以从左侧开始和从右侧 开始建设物流站都可以。 考虑最左侧的居民点0能覆盖到这个点的物流站有两个分别位于位置1和位置2这两个物流站至少要建一个当前看来位于位置2的物流站更优因为它可以覆盖更多居民点。对于整个方案来说如果选择在位置1建设物流站那么还需要覆盖{3,4,5,6,7,8}居民点如果选择在位置2建设物流站那么还需要覆盖{5,6,7,8}居民点是前者的子集。所以选择在位置2建设物流站对于整个方案来说是最优的选择。 未被覆盖的居民点5也用类似的思路分析在位置4和位置6中选择左侧增加的服务范围越大剩余需要覆盖的居民点越少这种贪心的思路可以保证每一步决策都是全局最优的。
n4#物流站地址个数
L8#物流运输线路的长度
X[4,1,6,2]#Xi表示第i个物流站选址的坐标
a[3,1,2,2]#ai。表示第i个物流站选址的服务距离
best[]#存放最优物流站选址的坐标索引
def Solve():r0#当前未覆盖的最左侧的居民点num0#物流站数量while(rL):# 寻找下一个物流站选址nex-1for i in range(n):if (X[i]-a[i]r) and (rX[i]a[i]):if nex-1 or X[nex]a[nex]X[i]a[i]: #居民点i比nex更优nexibest.append(nex)#如果没有任何物流站可以覆盖坐标r的居民点返回--1if nex-1:return -1#更新r和numrX[nex]a[nex]1num1return num,bestprint(Solve()) 既然这种贪心算法的思路可以得到全局最优解那么为什么在前面的二维平面建物流站时不能用贪心算法得到最优解呢?因为二维比一维要复杂得多比较两个物流站选址的优劣时关键是要比较决策后仍需解决的问题这在二维平面中是很困难的。 例如在图中要比较物流站选址1和物流站选址3在物流站选址1及建立物流站后还需要再覆盖居民点{(1,2),(1,1),(2,0),(3,0)}在物流站选址3处建立物流站后还需要再覆盖居民点{(1,2),(-4,1),(-1,1),(-2,0),(-3,-2)}这两个集之间没有包含或被包含的关系也就没办法直接判断两种决策的优劣。
回合制游戏 小余回到家里打开计算机开始玩一个回合制游戏。在该回合制游戏中小余扮演勇者在前往拯救公主的路上魔王派出了n只怪物阻挡勇者的前进每个怪物都有一定的血量游戏人物的生命值hi和攻击力ai。 每个回合中首先所有未被打败的怪物会一哄而上攻击小余扮演的勇者第i只怪物会造成ai点的伤害勇者受到的伤害等于每个怪物造成的伤害总和。 当然勇者也会攻击勇者一次只能选择其中一只怪物进行攻击第i个怪物需要攻击hi次才能被打败。 勇者不能逃避必须选择攻击现在用算法采取最优决策规划攻击每个怪物的顺序计算出勇者打败所有怪物时受到的最小伤害。 数据格式 n5表示5个怪物。 a[1,3,2,6,3]ai表示第i个怪物每回合可造成ai的伤害。 h[9,4,2,3,3],hi表示第i个怪物需要hi回合才能被打败。
思路 如果只有一只怪物打败它需要h0回合每回合受到a0的伤害总共受到的伤害就是a0*h0。 如果有两只怪物其中一只a02,h02,另一只a13,h14。
从怪物攻击力的角度考虑第2只怪物的攻击力更大每回合对勇者的伤害更大所以要优先打败第2只怪物。从回合数的角度考虑打败第2只怪物需要的回合数更多这意味着如果先打败第2只怪物则第1只怪物对勇者造成伤害的回合数会更多所以优先打败第1只怪物。
两只怪物判断函数如下
n5 #怪物数量
a[1,3,2,6,3]#ai表示第i个怪物每回合可造成ai的伤害。
h[9,4,2,3,3]#hi表示第i个怪物需要hi回合才能被打败。def compare(num1,num2):判断怪物num1,num2应该优先打败谁:param num1: 怪物1位置索引:param num2: 怪物2位置索引:return:#计算先打败怪物num1时受到的伤害damage1(a[num1]a[num2])*h[num1]a[num2]*h[num2]# 计算先打败怪物num2时受到的伤害damage2 (a[num1] a[num2]) * h[num2] a[num1] * h[num1]#比较两个伤害决定先打败那一只怪物if damage1damage2:print(damage1:,damage1)print(damage2:,damage2)return Trueelse:print(damage1:, damage1)print(damage2:, damage2)return False
print(compare(0,1))有两只怪物时应该如何攻击的问题解决了那么有n只怪物呢此时需要一个排序算法。本题的解法本质就是一个自定义排序只是传统的直接比较数字大小变成了用compare(num1,num2)比较
n5 #怪物数量
a[1,3,2,6,3]#ai表示第i个怪物每回合可造成ai的伤害。
h[9,4,2,3,3]#hi表示第i个怪物需要hi回合才能被打败。def compare(num1,num2):判断怪物num1,num2应该优先打败谁:param num1: 怪物1位置索引:param num2: 怪物2位置索引:return:#计算先打败怪物num1时受到的伤害damage1(a[num1]a[num2])*h[num1]a[num2]*h[num2]# 计算先打败怪物num2时受到的伤害damage2 (a[num1] a[num2]) * h[num2] a[num1] * h[num1]#比较两个伤害决定先打败那一只怪物if damage1damage2:return Trueelse:return False
#print(compare(1,2)) #False#排序
def sortArray(n,a,h):快速排序:param n:n5 #怪物数量:param a: a[1,3,2,6,3]#ai表示第i个怪物每回合可造成ai的伤害。:param h: h[9,4,2,3,3]#hi表示第i个怪物需要hi回合才能被打败。:return:# selection sortnums[i for i in range(n)] #怪物位置索引for i in range(n):for j in range(i,n):if compare(i,j):#如果应该优先打败怪物ipasselse:#如果应该优先打败怪物j。则j和i位置变换nums[i],nums[j] nums[j],nums[i]a[i], a[j] a[j], a[i]#攻击交换h[i], h[j] h[j], h[i] # 回合交换return numsnumssortArray(n,a,h)
print(排序结果,nums)#[3, 4, 2, 1, 0]
#计算勇者受到的总伤害
damage0
round0
for i in range(n):roundnums[i]*h[i]#回合数增加damageround*a[i]print(总伤害,damage)快速包装 小余在物流站建立一套自动化快递打包系统。只需要把快递摆放在传送带上传送带就会自动将货物运输到打包机械臂下方打包机械臂会根据货物调整到合适的大小只需要1min就可以完成一件快递的打包工作。等机械臂打包完成后传送带才会慢慢移动送来下一件货物。 每件快递大小不一并已知每件快递的高度和长度。打包台会依次对传送带上的每件快递进行打包特别地如果后一件快递的高度和长度分别都不大于当前快递的高度和长度那么机械臂打包完当前的快递后不需要调整即可立即对后一件快递进行打包否则需要1min来做调整此外第1件快递打包时也需要花时间调整。小余想要尽可能提高打包效率请你计算最少需要多久才能完成打包。 输入格式 n6 表示快递的数量 L[8,5,7,4,5,3] 。Li表示第 i件快递的高度。 W[8,7,6,4,7,7]。Wi表示第i件快递的长度。 思路每件快递打包需要的时间都是1min所以需要缩短打包做调整的时间可以再进一步把这些快递分到若干个队列中再对每个队列中的快递打包时打包只需在队首做一次调整需要用最少的队列容纳所有的快递。 1 在每个队列中队首的高度和长度最大后续每个货物都比前一个相等或者小。 2 用最少的队列。
方案如下 先把货物排序然后进行如下 1如果没有任何队列可以容纳某快递那么就新建一个队列容纳它。 2如果有队列都能容纳该快递那么一定不要新建队列。 3如果有多个队列可以容纳这件快递那么把它放在最早出现的队列末尾。 #快递结构体
class kuaidi:def __init__(self,Li,Wi):self.LLi #快递高度self.WWi#快递长度n6 #表示快递的数量
L[8,5,7,4,5,3] #Li表示第 i件快递的高度。
W[8,7,6,4,7,7]#Wi表示第i件快递的长度
lis[] #快递结构题数组
for i in range(n):lis.append(kuaidi(L[i],W[i]))def compare_parkage(a,b):比较两个快递 。先比较高度再比较长度:param a:快递1:param b:快递2:return:if a.L!b.L:#快递1高度是否大于快递2return a.Lb.Lelse: #否则比较长度return a.W b.W# 排序def sortArray(n, lis):根据问题自定义快速排序:param n: 表示快递的数量:param lis: #快递结构题数组:return:for i in range(n):for j in range(i, n):if compare_parkage(lis[i], lis[j]): # 如果快递i 快递j 比较passelse:# 则j和i位置变换lis[i], lis[j]lis[j], lis[i]return lis
lis1sortArray(n,lis) #排序后的快递组
for i in range(n):print(第%d个快递,高度为%d,长度为%d%(i,lis[i].L,lis[i].W))#构建队列
queue_num0 #队列数量初始化为0
tail[] #初始化每个队列的队尾,最多n个队尾
for i in range(n):tail.append(kuaidi(Li0,Wi0))for i in range(n):#遍历每个快递flagTruefor j in range(queue_num):#遍历每个队列#找到最早出现的能容纳这件快递的队列if (tail[j].Llis1[i].L) (tail[j].Wlis1[i].W):tail[j]lis1[i]flagFalsebreak#如果没有找到能容纳这件快递的队列则新建一个队列if flag:tail[queue_num]lis1[i]queue_num1
print(--------------结果-----------------)
print(队列数量:%d快递数量:%d%(queue_num,n))
