算法设计与分析 课件 7.5-回溯法 - 典型应用 - 子集树实现 - 0-1背包问题

算法设计与分析回溯法—0-1背包问题信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版voidBackTrack(intt){ if(t>n)Output(x); else for(inti=0;i<=1;i++){ x[t]=i; if(Constraint(t)&&Bound(t))BackTrack(t+1); }}解空间树：0-1背包问题子集树defOutput():#输出最优解和最优值

globalbestpprice=0.0foriinrange(n+1):ifx[i]:price+=v[i]ifprice>bestp:bestp=priceforiinrange(1,n+1):bestx[i]=x[i]defConstraint(t):#约束函数

contain=0.0foriinrange(t+1):ifx[i]:contain+=w[i]ifcontain<=c:#c表示背包容量

returnTrueelse:returnFalse思考：代码存在什么缺点？0-1背包问题思考：限界函数该如何设计？defBacktrack(t):globalcp,bestp,cwift>n:#到达叶结点

ifcp>bestp:bestp=cpforiinrange(1,n+1):bestx[i]=x[i]returnifcw+w[t]<=c:#搜索左子树

x[t]=1cw+=w[t]cp+=v[t]Backtrack(t+1)cw-=w[t]cp-=v[t]ifBound(t+1)>bestp:#搜索右子树

x[t]=0Backtrack(t+1)引入两个全局变量：cp:当前背包中物品的价值cw:当前背包中物品的重量0-1背包问题限界函数的设计defBound(t):#计算上界

cleft=c-cw#剩余容量

b=cpr=[]#记录剩余物品的重量和价值

foriinrange(t,len(w)):r.append([w[i],v[i]])r.sort(key=lambdax:x[1]/x[0],reverse=True)#定义排序规则：按照物品单位重量价值从大到小，lambda为虚拟函数。

foriinr:ifi[0]<cleft:#无法全部

b+=i[1]//i[0]*cleft#装满背包

breakelse:cleft-=i[0]b+=i[1]returnb0-1背包问题0-1背包问题defBacktrack(t):globalcp,bestp,cwift>n:#到达叶结点

ifcp>bestp:bestp=cpforiinrange(1,n+1):bestx[i]=x[i]returnifcw+w[t]<=c:#搜索左子树

x[t]=1cw+=w[t]cp+=v[t]Backtrack(t+1)cw-=v[t]cp-=p[t]ifBound(t+1)>bestp:#搜索右子树

x[t]=0Backtrack(t+1)0-1背包问题defBacktrack(t):globalcp,bestp,cwift>n:#到达叶结点bestp=cpforiinrange(1,n+1):bestx[i]=x[i]returnifcw+w[t]<=c:#搜索左子树

x[t]=1cw+=w[t]cp+=v[t]Backtrack(t+1)cw-=w[t]cp-=v[t]