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

算法设计与分析

回溯法—0-1背包问题;voidBackTrack(intt)

{

if(tn)Output(x);

else

for(inti=0;i=1;i++){

x[t]=i;

if(Constraint(t)Bound(t))

BackTrack(t+1);

}

};defOutput():#输出最优解和最优值

globalbestp

price=0.0

foriinrange(n+1):

ifx[i]:

price+=v[i]

ifpricebestp:

bestp=price

foriinrange(1,n+1):

bestx[i]=x[i]

defConstraint(t):#约束函数

contain=0.0

foriinrange(t+1):

ifx[i]:

contain+=w[i]

ifcontain=c:#c表示背包容量

returnTrue

else:

returnFalse;思考：

限界函数该如何设计？;限界函数的设计;;0-1背包问题;选择题：

0-1背包问题的解空间树形式是（）。

A:排列树

B:子集树