DP0-1背包

Written with StackEdit.

背包问题的大致特征

给定$C$,$(w_i,v_i)$求$max\sum x_i{v}_i\le C,x_i\in Interval$

0-1背包问题

0-1是最简单的背包问题,这里$interval\in \{0,1\}$

0-1递推关系

设$P(i,w)$为在序列前i个中选取总重不超过w的,使得权值最大. 则$$\begin{gathered} \forall i,w, \\ P(i,w)=Max\{P(i-1,w),P(i-1,w-w_i)+v_i\} \end{gathered}$$ 也就是是否选入第i个.

0-1边界条件

i=0时P=0.w=0时P=0.当wi>W时(第i个成员的权值大于分要求权值),已经选满,不能再选.也为了保证$0\le w_i$

实现

递归

很简单,直接按照状态转移填. 虽然会爆栈hhhhh

非递归

构建二维矩阵: 行是前i个元素 列是限制的重量 扫描方式是逐行扫描记忆化.

代码

递归

''' @Description: @Date: 2019-10-31 10:56:33 @Author: I-Hsien @LastEditors: I-Hsien @LastEditTime: 2019-10-31 11:22:57 ''' def build(set,maxop:int):#修剪序列当递归调用时 if maxop==0 or set==[]: return 0 if set[-1][0]>maxop: return build(set[:-1],maxop) else: return max(build(set[:-1],maxop),build(set[:-1],maxop-set[-1][0])+set[-1][1]) if __name__=="__main__": maxweight=int(input())#C array=input().split()#weight brray=input().split()#value assert(len(array)==len(brray)) setop=[]#int list for i in range(len(array)): setop.append((int(array[i]),int(brray[i])))#setop:[(weight,value)] print(build(setop,maxweight))

输入:

总重量限制重量序列价值序列

输出: 最大价值

非递归

记忆化搜索.横向扫描填表. 注意可以忽略weight=0的一列,初始化置为0.

''' @Description: 改进,非递归 @Date: 2019-10-31 11:39:57 @Author: I-Hsien @LastEditors: I-Hsien @LastEditTime: 2019-10-31 12:11:50 ''' import numpy as np def build(set,maxop:int): table=np.zeros((len(set),maxop+1))# An empty table for i in range(len(set)): for j in range(1,maxop+1):#[1]-[maxop] if set[i][0]>j: table[i][j]=table[i-1][j] else: table[i][j]=max(table[i-1][j],table[i-1][j-set[i][0]]+set[i][1]) #print("max in",table[i-1][j],table[i-1][j-set[i][0]]+set[i][1]) #print("set",i,j,table[i][j]) #print(table) return table[-1][-1] if __name__=="__main__": maxround=(input().split()) maxweight=int(maxround[0])#C round=int(maxround[1]) setop=[]#int list for _ in range(round): temp=input().split() setop.append((int(temp[0]),int(temp[1])))#[(weight,value)] print(int(build(setop,maxweight)))

明显的存在大量无用数据,在limit很大时内存占用过大.优化方法参见https://zhuanlan.zhihu.com/p/30959069,暂且留一个坑在这…