算法设计与分析的常用十大方案
发表于:2023-02-15 |
字数统计: 3k | 阅读时长: 12分钟 | 阅读量:

01背包问题(最优解问题)

就是现在有一个体积为c的背包,现在要装一些东西,这些东西有体积和价值,现在要求一个最优解,
也就是在c之内,放最大价值的物品
目的是限制化重量下,求最大价值

蛮力法

使用蛮力法就是,遍历每一种方案,对于每一个物品都要枚举一次看看是否放入背包,最后比较每一种方案的价值
(遍历每一种方案)

def bag01_force(n,w,value,weight):
	"""
	蛮力法求解
	n :物品数量
	w :背包体积
	value :物品价值
	weight :物品体积
	return 能放入的物品最大价值
	"""

	# 返回值

​	res = 0
​	

# 蛮力法 遍历每一种方案,n个物品,每一个物品都有两种状态,放入或者不放入背包,所以一共有

# 2**n种状态

# 1 0 1

# 2 10 01 00 11

for i in range(2**n):

	# 方案体积

​	total_weight = 0

	# 方案价值

​	total_value = 0

	# 第二层循环,每一种方案下遍历每一件物品

​	for j in range(n):

		# 判断方案i是否选择了物品j,如果被选择,那么背包中体积与价值发生变化

		# i是一个整数,j是一个0到n-1的整数

		# 1<<j 表示1左移j位

		# 位与运算,结果如果不为0,那么表示在该位上都为1,也就是j被选择了

		if (i & (1<<j)) != 0:
			total_weight += weight[j]
			total_value += value[j]
	

	# 判断,目的体积要小于背包容量

	if total_weight <= w:

		# 求最大价值

		res = max(res,total_value)
return res

“””
当i==0时,代表没有选择物品

i==1,第一种方案,j==0,第一个物品 1<<0 = 1 1 & 1 =1 代表在第i==1种方案下,第j==0(第一个物品)
被放进背包。
j == 1 表示第二个物品 1 << 1 = 10 1 & 10 = 0 没有被选择
j == 2,3,4…n-1

i == 2 j==0,1,2,,3…n-1

O(n) = n * 2 **n
“””

减治法

把一个大问题分解成几个小问题,递归求解子问题,合并子问题的解得到大问题的解(缩小问题规模)

第i个物品价值:value[i] 体积:weight[i],背包容量C

第i个物品,要么选,要么不选

1、前n-1个物品选择中,容量 C-weight[n] 选n

2、前n-1个物品选择中,容量 C 不选n

递归

def bag01(weight,value,n,c):
	# 背包容量为0或者物品数量为0,递归出口
	if c == 0 or n == 0
		return 0
	if weight[n-1] > c:
		return bag01(weight,value,n-1,c)
		

return max(value[n-1] + bag01(weight,value,n-1,c - weight[n-1]),bag01(weight,value,n-1,c))

循环(动态规划)

def bag01(n,c,weight,value):
	# 保存最终结果,c+1(存储了0-c的所有结果)
	dp = [0] * (c + 1)
	# 第一层循环,遍历物品
	for i in range(n):
		# 倒序遍历
		# 枚举第i物品,容量从c开始,枚举容量从大到小
		for j in range(c,weight[i] -1,-1):
			# 当前容量为j时,选或者不选第i个物品,取最大值,来确定这个物品是否放入背包
			# 如果加入,dp[j] == dp[j - w[i]] + v[i]
			# 不加入,dp[j]
			dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
	return dp[c]

分治法

分治法是把一个问题分解成子问题,再把子问题分解成更小的问题,直到子问题容易解决就把解合并。(分解问题)

n个物品,重量w1,w2,w3。。。wn。价值v1,v2…vn

容量为c,c-weight[i] > 0

max(value)

把物品分成两组,考虑每一组是否被选择。

#递归
def bag01(n,c,weight,value):
	# 物品数量为0或者背包容量为0
	if n==0 or c == 0:
		return 0
	# 物品不能放入背包
	if weight[n-1] > c:
		# 不考虑当前物品
		return bag01(n-1,c,weight,value)
	else:
		# 递归解决剩下问题,(放和不放,最大值)
		return max(value[n-1] + bag01(n-1,c-weight[n-1]),bag01(n-1,c.weight,value))

迭代(循环模拟递归,需要用变量来保存中间状态)

def bag01(n,c,weight,value):
	dp = [0] * (c+1)
	for i in range(1,n+1):
		for j in range(c,weight[i-1] -1,-1):
			dp[j] = max(dp[j],dp[j-weight[i-1]]+value[i-1])
	return dp[c]

分治法重点是把物品不断的切割,分别考虑每组物品是否被选择

减治法重点不断缩减背包容量,利用放入或者不放入物品

变治法

对问题进行变形,将问题转换成简单的问题

例如:减小问题规模n —— n/2

背包容量从小到大排序,利用分治法把大问题分解为小问题,然后减治法把子问题合并起来

def bag01(weight,value,c,n):
	# 中间状态,f[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值
	f = [[0 for j in range(c+1)] for i in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,c+1):
			# 第i个物品不能放
			if j < weight[i-1]:
				# 第i个物品取第i-1个物品的状态
				f[i][j] = f[i-1][j]
			else:
				# 取第i-1个物品的状态和第i个物品放入的状态的较大值
				f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]])
	return f[n][c]

时空权衡(基于计算机)

如果想要时间效率最优,可以用动态规划,如果想要空间占用少,可以使用贪心或者滚动数组(将多余空间删去)

滚动数组(模2)

占用空间较小

def bag01(weight,value,c,n):
	f = [[0 for j in range(c+1)] for i in range(2)]
	for i in range(1,n+1):
		for j in range(1,c+1):
			# i物品数 j容积
			# 第i个物品不进背包的情况(% 取余)
			f[i % 2][j] = f[(i-1) % 2][j]
			# 第i个物品不能放
			if j >= weight[i-1]:
				# 第i个物品取第i-1个物品的状态
				f[i % 2][j] = f[(i-1) % 2][j]
			else:
				# 取第i-1个物品的状态和第i个物品放入的状态的较大值
				f[i % 2][j] = max(f[i % 2][j],f[(i-1) % 2][j-weight[i-1]])
	return f[n][c]

动态规划(解决最优解问题的方法)

一种求解多阶段决策问题的方法,一种面向最优化的递归计算技巧

用于求解分段函数的最值。它通过以一定顺序对复杂问题进行分解,以避免重复的计算。

并以类似递推的方式,通过对更小的子问题的解的组合得到原问题的解。

1、分解问题,对于分解之后的若干子问题·,定义一个状态。通过状态转移方程,将子问题的解转化成原问题的解

对于每一个物品i,枚举它的体积j,计算f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]),

def bag01(weight,value,c,n):
	# 中间状态,f[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值
	f = [[0 for j in range(c+1)] for i in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,c+1):
			# 第i个物品不能放
			if j < weight[i-1]:
				# 第i个物品取第i-1个物品的状态
				f[i][j] = f[i-1][j]
			else:
				# 取第i-1个物品的状态和第i个物品放入的状态的较大值
				f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]])
	return f[n][c]

贪心(最优解问题)并不总能得到全局最优解

n件物品放入容量为c的背包中,(可不全部放入)使得背包中物品价值最大。

较好的近似解

问题分解,求每一个小问题的最优解。

1、单位重量价值最大的物品先放,直到背包无法再放。(贪心选择性质)

def bag01(value,weight,n,c):
	# 物品的单位重量价值
	meimei = [value[i]/weight[i] for i in range(n)]
	# 排序(逆序,从大到小的顺序)按照价值重量比排序后的物品索引数组
	meimei = sorted(range(n),key=lambda i: meimei[i],reverse=True)
	total_value = 0
	# 是否放入背包的数组
	bag = [0] * n
	for i in meimei:
		if weight[i] <= c:
			bag[i] = 1
			total_value += value[i]
			c -= weight[i]
		else:
			# 计算部分放入背包
			bag[i] = c/weight[i]
			total_value += value[i] * (c/weight[i])
			break
	return total_value,bag

迭代改进(优化算法)并不总能得到全局最优解,较好的近似解

基本思想:每一次迭代中,根据当前解,确定一个方向,并且在方向上的解有所改进。

具体步骤:

1、初始化解,将解初始化为一个可行解。(全放和全不放)

2、迭代改进,每一次迭代中,选择一个方向,感觉该方向的优化目标,生成一个新解,并比较当前解。

3、判断终止条件,判断解是否满足问题要求

def bag01(value,weight,n,c):
	# 初始化解
	select_items = [0] * n
	total_value = 0
	

while c >0:

	# 计算性价比,并按照性价比从大到小排序

	ratios = [(value[i] / weight[i],i) for i in range(n)]
	ratios.sort(reverse=True)
	

	# 尝试放入物品

	for ratio,i in ratios:
		if weight[i] <= c:
			c -= weight[i]
			select_items[i] = 1
			total_value += value[i]
	

	# 判断终止条件

	if all(select_items):
		break
return total_value,select_items

回溯与分支界限

回溯(全局搜索)逐步构造方案来找到所有解

首先选择一个决策,直到找到最终的解或者无法前进,无法前进返回上一层,继续下一个决策。

关键:剪枝(避免重复)

分支界限(局部搜索找到最优解)逐步将空间缩小来找到问题的最优解。

根据规则生成一组候选解,对这组解评估,选出一个最优解,再根据最优解生成下一组,知道找到最终解

关键:剪枝(避免重复)

01背包中,回溯法:可以用于找到所有可能的解。分支界限:用于找到最优的解。

回溯法

def bag01(c,n,weight,value):
	def back(i,c_weight,c_value):
		'''
		i : 第i件物品
		c_weight:当前背包重量
		c_value:当前背包价值
		'''
		nonlocal max_value
		if c_weight > c:
			return
		if c_value > max_value:
			max_value = c_value
		if i == n:
			return
		# 不选第i件物品
		back(i+1,c_weight,c_value)
		# 选第i件物品
		back(i+1,c_weight+weight[i],c_value+value[i])
	max_value = 0
	back(0,0,0)
	return max_value

分支界限(对回溯算法的改进。剪枝)

def bag01(c,n,weight,value)# 创建一个节点类,保存当前状态和状态的价值上界。

	class Node:
		def __init__(self,level,value,weight):

			# level表示当前节点的深度

			self.level = level
			self.value = value
			self.weight = weight

		# 定义对象之间的<比较。

		def __lt__(self,other):
			return self.value > other.value

	# 创建一个优先队列,用来保存待扩展的节点,初始队列只有一个节点,表示当前状态为空

	nodes = [Node(0,0,0)]
	max_value = 0
	while nodes:
		node = nodes.pop(0)

		# 代表选完了所有的节点

		if node.level == n:
			if node_value > max_value:
				max_value = node_value
			continue
		

	# bound 存储计算得到的价值上界

	bound = node_value

	# 不选第i件物品

	for j in range(node.level,n):

		# 装不下

		if node.weight + weight[j] > c:

			# 取物品的部分

			bound += (c - node.weight) / weight[j] * value[j]
			break
		bound += value[j]

	# 价值上界大于已知的最大价值

	if bound > max_value:
		nodes.append(Node(node.level+1,node.value,node.weight))
	

	# 选第i件物品

	bound = node.value + value[node.level]
	weight = node.weight + weight[node.level]
	if weight <= c and bound > max_value:
		max_value = bound
	if bound > max_value:
		nodes.append(Node(node.level+1,bound,weight))
return max_value
上一篇:
操作系统复习笔记
下一篇:
博客开发日记