最新回溯法解决01背包问题教学讲义PPT

01背包问题（回溯法） 回溯法是⼀个既带有系统性⼜带有跳跃性的搜索算法。

它在包含问题的所有解的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索⾄解空间树的任意⼀结点时，先判断该结点是否包含问题的解。

如果肯定不包含，则跳过对该结点为根的⼦树搜索，逐层向其祖先结点回溯；否则，进⼊该⼦树，继续按深度优先策略搜索。

问题的解空间⽤回溯法解问题时，应明确定义问题的解空间。

问题的解空间⾄少包含问题的⼀个(最优)解。

对于 n=3 时的 0/1 背包问题，可⽤⼀棵完全⼆叉树表⽰解空间，如图所⽰：求解步骤1)针对所给问题，定义问题的解空间；2)确定易于搜索的解空间结构；3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。

常⽤的剪枝函数：⽤约束函数在扩展结点处剪去不满⾜约束的⼦树；⽤限界函数剪去得不到最优解的⼦树。

回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（⾮递归）两种⽅法，但⼀般情况下⽤递归⽅法实现回溯法。

算法描述 解 0/1 背包问题的回溯法在搜索解空间树时，只要其左⼉⼦结点是⼀个可⾏结点，搜索就进⼊其左⼦树。

当右⼦树中有可能包含最优解时才进⼊右⼦树搜索。

否则将右⼦树剪去。

代码：public class Knapsack_Problem01 {double m=100; //背包最⼤容量int n=5; //物品的个数int[] w = {10,20,30,40,50}; //第i个物品的重量int[] v = {20,30,65,40,60}; //第i个物品的价值int[] a = new int[n]; //记录在树中的移动路径,为1的时候表⽰选择该组数据，为0的表⽰不选择该组数据int maxvalue = 0; //背包的最⼤权重值public static void main(String[] args){Knapsack_Problem01 p = new Knapsack_Problem01();p.Search(0);}public void Search(int i) //i表⽰递归深度{if(i>=n){CheckMax();}else {a[i] = 0;Search(i+1);a[i] = 1;Search(i+1);}}public void CheckMax(){int weight = 0;int value = 0;for(int i=0;i<n;i++) //判断是否达到上限{if(a[i] == 1){weight = weight + w[i];value = value + v[i];}}if(weight <= m){if(value >= maxvalue){maxvalue = value;System.out.print("最⼤价值是：" + maxvalue +" ");System.out.print("所选取的物品为(1代表选中，0代表不选中)： ");for(int j=0;j<n;j++){System.out.print(a[j]);System.out.print(' ');}System.out.print('\n');}}}}。

回溯法解决0-1背包问题问题描述： 有n件物品和⼀个容量为c的背包。

第i件物品的价值是v[i]，重量是w[i]。

求解将哪些物品装⼊背包可使价值总和最⼤。

所谓01背包，表⽰每⼀个物品只有⼀个，要么装⼊，要么不装⼊。

回溯法： 01背包属于找最优解问题，⽤回溯法需要构造解的⼦集树。

在搜索状态空间树时，只要左⼦节点是可⼀个可⾏结点，搜索就进⼊其左⼦树。

对于右⼦树时，先计算上界函数，以判断是否将其减去，剪枝啦啦！上界函数bound():当前价值cw+剩余容量可容纳的最⼤价值<=当前最优价值bestp。

为了更好地计算和运⽤上界函数剪枝，选择先将物品按照其单位重量价值从⼤到⼩排序，此后就按照顺序考虑各个物品。

#include <stdio.h>#include <conio.h>int n;//物品数量double c;//背包容量double v[100];//各个物品的价值double w[100];//各个物品的重量double cw = 0.0;//当前背包重量double cp = 0.0;//当前背包中物品价值double bestp = 0.0;//当前最优价值double perp[100];//单位物品价值排序后int order[100];//物品编号int put[100];//设置是否装⼊//按单位价值排序void knapsack(){int i,j;int temporder = 0;double temp = 0.0;for(i=1;i<=n;i++)perp[i]=v[i]/w[i];for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++)if(perp[i]<perp[j])//冒泡排序perp[],order[],sortv[],sortw[]{temp = perp[i];perp[i]=perp[i];perp[j]=temp;temporder=order[i];order[i]=order[j];order[j]=temporder;temp = v[i];v[i]=v[j];v[j]=temp;temp=w[i];w[i]=w[j];w[j]=temp;}}}//回溯函数void backtrack(int i){double bound(int i);if(i>n){bestp = cp;return;}if(cw+w[i]<=c){cw+=w[i];cp+=v[i];put[i]=1;backtrack(i+1);cw-=w[i];cp-=v[i];}if(bound(i+1)>bestp)//符合条件搜索右⼦数backtrack(i+1);}//计算上界函数double bound(int i){double leftw= c-cw;double b = cp;while(i<=n&&w[i]<=leftw){leftw-=w[i];b+=v[i];i++;}if(i<=n)b+=v[i]/w[i]*leftw;return b;}int main(){int i;printf("请输⼊物品的数量和容量：");scanf("%d %lf",&n,&c);printf("请输⼊物品的重量和价值：");for(i=1;i<=n;i++){printf("第%d个物品的重量：",i);scanf("%lf",&w[i]);printf("价值是：");scanf("%lf",&v[i]);order[i]=i;}knapsack();backtrack(1);printf("最有价值为：%lf\n",bestp);printf("需要装⼊的物品编号是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",order[i]);}return 0;}时间复杂度分析： 上界函数bound()需要O(n)时间，在最坏的情况下有O(2^n)个右⼦结点需要计算上界，回溯算法backtrack需要的计算时间为O(n2^n)。

//h(i)表示在当前扩展节点处x[t]的第i个可选值
实 现 递 归
} }
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --;
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --; 分析：
算法设计与分析 >回溯法
5、回溯法解题步骤: 1).针对所给问题,定义问题的解空间 2).确定解空间结构. 3).以深度优先方式搜索解空间.
算法模式 Procedure BACKTRACK(n)； {k:=l； repeat if TK (x1,x2,...xK-1 )中的值未取遍 then { xK:＝TK (x1，x2，..., x K-1 )中未取过的一个值； if BK (x1, x2, ..., x K) then //状态结点(x1,...xk)被激活 if k＝n then output(x1, x2, ..., xk) //输出度优先 e1se k:＝k-l； //回溯 until k＝0； end；{BACKTRACK}
if (Constraint(t)&&Bound(t) ) Backtrack(t + 1)； if语句含义：Constraint(t)和Bound(t)表示当前扩展 节点处的约束函数和限界函数。 Constraint(t): 返回值为true时，在当前扩展节点处 x[1:t]的取值问题的约束条件，否则不满足问题的约束条 件，可剪去相应的子树 Bound(t): 返回的值为true时，在当前扩展节点处 x[1：t]的取值为时目标函数越界，还需由Backtrack(t+1) 对其相应的子树做进一步搜索。否则，当前扩展节点处 x[1：t]的取值是目标函数越界，可剪去相应的子树 for循环作用：搜索遍当前扩展的所有未搜索过的 子树。 递归出口：Backtrack(t)执行完毕，返回t-1层继续 执行，对还没有测试过的x[t-1]的值继续搜索。当t=1时， 若以测试完x[1]的所有可选值，外层调用就全部结束。

begin a[i]:=j;//标识该物品的形状 m:=m-a[i]*j;//剩余空间变化 try[i+1];//下一个物体选择 m:=m-a[i]*j;//剩余空间变化 a[i]:=0; end; End.
递归概念
我们可以用choose(I,z)来表示后i个物品在只剩下v个体积的空间中取的最 大价值
所谓的背包问题，可以描画如下： 一个小偷打劫一个保险箱，发现柜子里有N
个不同大小与价值的物品，但小偷只需一 个容积为M的背包来装东西，背包问题就 是要找出一个小偷选择所偷物品的组合， 以使偷走的物品总价值最大。我们标识每 个物品的价为ＶI,大小是ZI
算法描画
对于0/1背包相关的问题我们有多种方法可 以处理
end;
end;
0/1背包问题的分析
该背包问题的目的在于求最优解，所以我们要用 回溯的方法将一切的解求出来，逐一比较求最优 秀的解；
对于每个节点的扩展只需两种类能够要不取，要 不不取，所以该搜索树为一个N层的二叉树。
解空间的长度是<=n。 解空间的组织方式是一棵2叉树，一个可行的解就
是从根节点到叶子节点的一条途径。每个解为一 个长度不超越N的0/1代码序列 控制战略那么是前面的选择没有超越背包的容量。
end;
for i:=算符最小值 to 算符最大值 do
begin
算符i作用于生成stack[k-1]产生子形状stack[k];
if stack[k]满足约束条件 then make(k+1);{假设不满足，那么经过for循环换一个算
算符扩展。注：假设在扩展stack[k].state时运用过全局变量，那么应插入假设干条语句，恢
二、回溯的通用描画算法
program 程序名；