常见经典算法AND背包问题

常见经典算法策略的特点、区别与联系

分治算法：

​ 分治法的设计思想是：将一个难以解决的大问题分解为多个规模较小的子问题，以便分而治之。如果原问题可以分为k个子问题，其中国内1<k<=n,且这k个子问题都可解，并可利用子问题计算出原问题的解，则可以选择分治法解决该问题。

​ 分治算法的特点：通过分治方法设计出的程序一般都递归算法，故分治法的计算效率可以用递归方程进行分析。但是分治与递归也有区别，分治是将原问题转换为若干个相似的小问题去解，而递归则是将原问题层层转化为一个与原问题相似的小问题然后再去求解。

贪心算法：

贪心算法指在求解问题的时候总是做出在当前情况下的最好的选择，不会考虑整体最优解，即只寻找局部最优解。不同的贪心策略会得到差异非常大的结果，如果希望对该问题使用贪心策略，则待求解的问题中的字问题需要具备无后效性——即某个状态以前的过程不会影响以后的状态，只与当前的状态有关。

贪心算法的特点：最优子结构性质和贪心选择性质。贪心选择性质指需要求解的问题的整体最优解可通过一系列局部最优解的选择来实现。对于每一个具体的问题，必须证明每一步所做的贪心选择最后都会达成一个全局最优解。最优子结构是指一个问题的最优解包含其子问题的最优解性质。

贪心算法与动态规划算法的区别和联系：贪心算法和动态规划算法都具有最优子结构的性质。但是动态规划算法中，每一步所做出的选择要依赖相关子问题的解，因此只有在求出相关子问题的解后才能做出选择。而贪心算法则不依赖全局解，仅仅依靠过去所做出的选择而不依赖将来所做出的选择，也不依赖子问题的解，即只选择局部最优解。

动态规划算法：

动态规划算法的基本思想是将需要求解的问题划分为若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。动态规划算法通常用于求解具有某种最优子结构性质的问题。在这类问题中，可能会有许多可行的解，但是期望找到具有最优值的解。基于动态规划法的算法设计通常按一下四个步骤进行：

1. 找出最优解的性质，并描述其结构特征。

2. 递归定义最优值。

3. 自底向上的方式计算最优质。

4. 根据计算最优值时得到的信息构造一个最优解。

通常，在步骤3中计算最优值时，需要记录更多的信息，以便在步骤4中快速构造出一个最优解。

动态规划算法的特点：动态规划算法一般具有最优子结构，重叠子问题两个性质。设计动态规划算法的第一步是分析最优结构，当带求解的问题中包含了其子问题的最优解时，就可以定义该问题具有最优子结构性质。而可以用动态规划方法求解的问题，应具有重叠子问题的性质。在用递归算法自顶向下尝试解决此类问题时，每次产生的问题并不一定是新问题，有些子问题会被反复计算多次从而造成计算资源的浪费。而动态规划算法通过利用这种子问题的重叠性，对每个子问题只求一次解，并将结果保存在一个表中，当再次需要解相同的问题时只需要从表中调出数据即可。

动态规划算法与分治算法的区别与联系：动态规划酸粉与分治法类似，基本思想都是将带求解的问题分解成很多子问题，先求子问题然后从这些子问题中得到原问题的解。与分治法不同的地方在于使用动态规划求解的问题其子问题不是相互独立的，而使用分治法求解的问题其子问题相互独立，若使用分治法去求解子问题不相互独立的问题，则分解得到的子问题数量太大从而使得计算时间大大增加。另外使用分治法求解问题的时候有些子问题会被重复计算，而使用动态规划法去求解的时候每个子问题只需要计算一次。

回溯算法：

回溯算法是搜索算法的一种，它在包含问题所有解的空间树中，按照深度优先的策略从root节点出发去搜索整个空间树。这种算法搜索到解空间的任意一个节点时，会首先判断该节点是否不包含问题的解，如果不包含则跳过以该节点为根的子树，逐层向其祖先节点回溯；否则进入该子树并继续按深度优先遍历进行搜索。

回溯法的特点：回溯法在求解的过程中需要回溯到树根，并且在搜索树中所有节点后才结束。而用回溯法搜索问题的任意一个解时，只需要搜到其中一个问题的解即可结束。

分支界限法

分支界限法是一种在问题的解空间树T上搜索问题解的算法，其特点是：在扩展节点出，首先生成器所有孩子节点，然后在从当前活动节点表中选择下一个扩展节点。为了有效的计算下一个活节点，加快搜索速度，就在每一个活节点处计算一个函数值，并根据已计算出的函数值从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间中具有最优解的分支推进，以便尽快找出一个最优解。

分支界限法与回溯法的区别与联系：二者类似，一般而言分支界限法与回溯法的求解目标不同：分支界限法的求解目标是找出解空间树T中满足约束条件的一个解，或者在满足约束条件的解中找一个使得目标函数极大活着极小的解，即某种意义下的最优解。而回溯法则是找出T中满足约束条件的所有解。由于解题目标不同，导致分支界限法和回溯法的搜索方式也不同，回溯法以深度优先的方式搜索T，而分支界限法以广度优先或最小耗费有限的方式搜索T。

参考取数问题的算法框架，写出0-1背包问题的3种算法，并写出找出最优解的算法

定义一下0-1背包问题中的变量：给定n个物品和一个背包，物品i的重量是wi，其价值为vi，背包容量为c。

动态规划算法

算法策略

与贪心算法不同的是，动态规划算法需要比较选择该物品和不选择该物品所导致的最终结果，然后在做出最佳选择。如果放入第i个东西后可以取得最大价值，则前i-1个物品也取到了最大价值，重量为w-w[i]。定义dp[i][j]为放入第i个物品后可以取得最大价值，则其状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] +price[i])。

核心算法：

def Dongtaiguihua(w,n,):
    listWV = [[0,0]]
    listTemp = []

    for i in range(n):
        listTemp = list(map(int, input().split()))  
        listWV.append(listTemp) 

    value = [[0 for i in range(w+1)] for j in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, w+1):
        	#若物品不能放到背包中
            if j < listWV[i][0]:
           		#价值与之前相同    
                value[i][j] = value[i-1][j] 
            else:   
            	#物品可以放到背包中，最大价值在两者之中取
                value[i][j] = max(value[i-1][j], value[i-1][j-listWV[i][0]] + listWV[i][1])

    return value

回溯法

算法策略

使用回溯法求解时，如果用wCur和vCur分别表示当前正在搜索的部分解中装入背包物体的总重量和总价值，用vBest表示当前正在搜索部分解的最大价值，则基本思路如下：

1. 把物体按单位价值降序排列
2. wCur vCur vBest初始化
3. 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。

核心算法：

'''
vbest：最大价值
vCur：背包价值
wCur：背包重量
x：list型，标记是否路径中是否包含了该节点
v:list型，存放所有物品的价值
w:list型，存放所有物品的重量
n：物品数量
c：背包容量
'''
def Huisu(vbest,vCur,wCur,x,w,v,n,c):
    if i>= n and vbest<vCur:
        vbest = vCur
    else:
        if wCur+w[i]<=c:
            x[i]=1
            wCur += w[i]
            vCur += v[i]
            # 下一个
            Huisu(i+1)
            wCur -= w[i]
            vCur -= v[i]
        x[i]=0
        # 下一个
        Huisu(i+1)
	# vbest中存放了最优解
    return vbest

贪心算法

理论上贪心算法只能够求解背包问题，没法求解0-1背包问题，但是本来应该作为第三种算法的分支界限算法跑到最后一问去了，还找不到其他算法就把贪心算法放这强行充3个挽尊了orz

算法策略

使用贪心选择求解0-1背包问题本质上还是计算单位重量价值最高的物品装到包里，但是与背包问题不同的地方在于这里没有办法对物品进行拆分，即在选择装入背包的物品时对每种物品i只有两个选择——装或者不装。不能将物品i装入背包多次，也不能只装入部分物品i，故使用该策略计算0-1背包问题的时候会存在背包装不满的情况，这符合贪心策略的最优解，即局部最优解；但是不符合整体最优解。

基本步骤

1. 计算出每种物品的单位重量价值vi/wi
2. 依贪心选择策略，将尽可能多的单位重量价值最高的物品（设其重量为wi）装进去
3. 将物品全部装完之后，背包内总重量未超过c则按单位价值排序选择重量不超过c-wi的下一个物品全部装进去。
4. 依此策略一直进行下去，一直到背包装满或者剩余空间不够装剩下的物品。

核心算法

# Listv:list型，存放所有物品的价值
# Listw:list型，存放所有物品的重量
def Tanxin(n,C,Listv,Listw):
	# 计算单位价值并排序
	value = [(x,Listv[x] / Listw[x], Listv[x], Listw[x]) for x in range(0,n)]
	value.sort(key=lambda x:x[1], reverse=True)

	# 开始放往包里放东西
	maxvalue = 0
	Listx = []
	for x,xi,vi,wi in value:
	    # 如果能放的下就全放进去
	    if vi <= C:
	        C -= wi
	        maxvalue += vi
	        Listx.append(x)
	# Listx中存放的是放进包的物品，maxvalue是使用贪心算法时包内物品的总价值	
	return Listx, maxvalue

算法Tanxin的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。

写出0-1背包问题的分支界限算法

算法策略

采用优先队列方式，按照物品的单位价值从大到小进行优先级排序，使用大根堆结构存储物品数据。构造上界函数maxbound( )计算当前结点下的价值上界，如果当前结点下的价值上界比当前的最优值大，则将当前结点加入堆中，否则剪去该节点下的所有路径(即剪去子集树的枝)，直到堆中所有结点均被弹出。基本步骤如下：

1. 把物体按单位价值降序排列

2. 节点的优先级由已装的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和

3. 算法首先检查当前扩展结点的左子树结点，若满足约束条件则加入优先队列中

4. 检查右子树结点，若满足约束条件则加入优先队列中

算法代码

def Fenzhijiexian(vw, limit):
	# 上界函数：计算当前结点下的价值上界
    def bound(v, w, j):
        if j >= len(vw) or w > limit:
            return -1
        else:
            while j < len(vw) and w + vw[j][1] <= limit:
                v, w, j = v + vw[j][0], w + vw[j][1], j + 1
            if j < len(vw):
                v += (limit - w) * vw[j][0] / (vw[j][1] * 1.0)
            return v
    # 分支限界算法求解01背包
    def traverse(v, w, j):
        nonlocal maxValue
        if bound(v, w, j) >= maxValue: # promising 
            if w + vw[j][1] <= limit:  # w/ j
                maxValue = max(maxValue, v + vw[j][0])
                traverse(v + vw[j][0], w + vw[j][1], j + 1)
            if j < len(vw) - 1:        # w/o j
                traverse(v, w, j + 1)
        return
    maxValue = 0
    traverse(0, 0, 0)
    return maxValue

先对 vw 按照单位重量的价值排序，然后利用 bound 函数确定价值上限。如果价值上限超过了已经出现的最大价值，再分别计算加上当前物品和不加当前物品的两种情况，否则就跳过。

参考链接

https://blog.csdn.net/qq_42939527/article/details/104043900

https://blog.csdn.net/yue_luo_/article/details/95097844

https://www.cnblogs.com/chenleideblog/p/11254578.html

https://blog.csdn.net/weixin_42260102/article/details/96008327

https://www.jlao.net/technology/10188/

王红珍,李竹林,延飞波.基于0-1背包问题的两种算法[J].信息技术,2011,35(02):27-29.

荣政主编. 数据结构与算法分析. 西安：西安电子科技大学出版社, 2012.02.