当前位置:首页 >> 计算机软件及应用 >>

回溯法和分支限界法解决0-1背包题


0-1 背包问题
计科 1 班 朱润华 2012040732 方法 1:回溯法 一、回溯法描述: 用回溯法解问题时,应明确定义问题的解空间。问题的解空间至少包含问题的一个(最 优)解。对于 0-1 背包问题,解空间由长度为 n 的 0-1 向量组成。该解空间包含对变量的所 有 0-1 赋值。例如 n=3 时,解空间为: { (0,0,0) , (0,1,0) , (0,0,1) , (1,0,0) , (0,1,1) , (1,0,1) , (1,1,0) , (1,1,1) } 然后可将解空间组织成树或图的形式, 0-1 背包则可用完全二叉树表示其解空间给定 n 种物品和一背包。 物品 i 的重量是 wi, 其价 值为 vi,背包的容量为 C。问:应如何选择装入背包的物品,使得装入背包中物品的总价值 最大? 形式化描述:给定 c >0, wi >0, vi >0 , 1≤i≤n.要求找一 n 元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi 达最大.即一个特殊的整数规划问题。

二、回溯法步骤思想描述: 0-1 背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空 间树时,只要其左儿子节点是一个可行节点,搜索就进入左子树。当右子树中有可能含有最 优解时,才进入右子树搜索。否则,将右子树剪去。设 r 是当前剩余物品价值总和,cp 是 当前价值;bestp 是当前最优价值。当 cp+r<=bestp 时,可剪去右子树。计算右子树上界的 更好的方法是将剩余物品依次按其单位价值排序,然后依次装入物品,直至装不下时,再装 入物品一部分而装满背包。 例如:对于 0-1 背包问题的一个实例,n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这 4 个物 品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物 品 4,然后装入物品 3 和 1.装入这 3 个物品后,剩余的背包容量为 1,只能装 0.2 的物品 2。 由此得一个解为[1,0.2,1,1],其相应价值为 22。尽管这不是一个可行解,但可以证明其价 值是最优值的上界。因此,对于这个实例,最优值不超过 22。 在实现时,由 Bound 计算当前节点处的上界。类 Knap 的数据成员记录解空间树中的节 点信息,以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处,仅要进入右 子树时才计算上界 Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界,因 为上界预期父节点的上界相同。 三、回溯法实现代码: #include "stdafx.h" #include <iostream> using namespace std; template<class Typew,class Typep> class Knap { template<class Typew,class Typep> friend Typep Knapsack(Typep [],Typew [],Typew,int); private: Typep Bound(int i);

void Backtrack(int i); Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp;//当前最后价值 }; template<class Typew,class Typep> Typep Knapsack(Typep p[],Typew w[],Typew c,int n); template <class Type> inline void Swap(Type &a,Type &b); template<class Type> void BubbleSort(Type a[],int n); int main() { int n = 4;//物品数 int c = 7;//背包容量 int p[] = {0,9,10,7,4};//物品价值 下标从 1 开始 int w[] = {0,3,5,2,1};//物品重量 下标从 1 开始 cout<<"背包容量为:"<<c<<endl; cout<<"物品重量和价值分别为:"<<endl; for(int i=1; i<=n; i++) { cout<<"("<<w[i]<<","<<p[i]<<") "; } cout<<endl; cout<<"背包能装下的最大价值为:"<<Knapsack(p,w,c,n)<<endl; return 0; } template<class Typew,class Typep> void Knap<Typew,Typep>::Backtrack(int i) { if(i>n)//到达叶子节点 { bestp = cp; return; } if(cw + w[i] <= c)//进入左子树 { cw += w[i];

cp += p[i]; Backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp)//进入右子树 { Backtrack(i+1); } } template<class Typew, class Typep> Typep Knap<Typew, Typep>::Bound(int i)// 计算上界 { Typew cleft = c - cw; // 剩余容量 Typep b = cp; // 以物品单位重量价值递减序装入物品 while (i <= n && w[i] <= cleft) { cleft -= w[i]; b += p[i]; i++; } // 装满背包 if (i <= n) { b += p[i]/w[i] * cleft; } return b; } class Object { template<class Typew,class Typep> friend Typep Knapsack(Typep[],Typew [],Typew,int); public: int operator <= (Object a)const { return (d>=a.d); } private: int ID; float d;

}; template<class Typew,class Typep> Typep Knapsack(Typep p[],Typew w[],Typew c,int n) { //为 Knap::Backtrack 初始化 Typew W = 0; Typep P = 0; Object *Q = new Object[n]; for(int i=1; i<=n; i++) { Q[i-1].ID = i; Q[i-1].d = 1.0 * p[i]/w[i]; P += p[i]; W += w[i]; } if(W <= c)//装入所有物品 { return P; } //依物品单位重量价值排序 BubbleSort(Q,n); Knap<Typew,Typep> K; K.p = new Typep[n+1]; K.w = new Typew[n+1]; for(int i=1; i<=n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; K.bestp = 0; //回溯搜索 K.Backtrack(1); delete []Q; delete []K.w;

delete []K.p; return K.bestp; } template<class Type> void BubbleSort(Type a[],int n) { //记录一次遍历中是否有元素的交换 bool exchange; for(int i=0; i<n-1;i++) { exchange = false ; for(int j=i+1; j<=n-1; j++) { if(a[j]<=a[j-1]) { Swap(a[j],a[j-1]); exchange = true; } } //如果这次遍历没有元素的交换,那么排序结束 if(false == exchange) { break ; } } } template <class Type> inline void Swap(Type &a,Type &b) { Type temp = a; a = b; b = temp; } 四、程序运行结果:

五、回溯法解决 0-1 背包问题复杂度分析: 计算上界需要 O(n)时间, 在最坏情况下有 O(2^n)个右儿子节点需要计算上界, 故解 0-1 背包问题的回溯算法所需要的计算时间为 O(n2^n)。 方法 2:分支限界法: 一、分支限界法描述: 给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 vi,背包的容量为 C。问:应如 何选择装入背包的物品,使得装入背包中物品的总价值最大? 形式化描述:给定 c >0, wi >0, vi >0 , 1≤i≤n.要求找一 n 元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi 达最大.即一个特殊的整数规划问题。 二、分支限界法步骤思想: 首先,要对输入数据进行预处理,将各物品依其单位重量价值从大到小进行排列。在优 先队列分支限界法中, 节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物 品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。 如果该左儿子结点是可行结点, 则 将它加入到子集树和活结点优先队列中。 当前扩展结点的右儿子结点一定是可行结点, 仅当 右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。 当扩展到叶节点时为问题 的最优值。 例如:0-1 背包问题,当 n=3 时,w={16,15,15}, p={45,25,25}, c=30。优先队列式分 支限界法:处理法则:价值大者优先。{}—>{A}—>{B,C}—>{C,D,E}—>{C,E}—>{C,J, K}—>{C}—>{F,G}—>{G,L,M}—>{G,M}—>{G}—>{N,O}—>{O}—>{}。 三、分支限界法解决 0-1 背包问题实现代码: //0-1 背包问题 分支限界法求解 #include "stdafx.h" #include "MaxHeap.h" #include <iostream> using namespace std; class Object { template<class Typew,class Typep> friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); public: int operator <= (Object a) const { return d>=a.d; } private: int ID; float d;//单位重量价值 }; template<class Typew,class Typep> class Knap; class bbnode

{ friend Knap<int,int>; template<class Typew,class Typep> friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); private: bbnode * parent; //指向父节点的指针 bool LChild; //左儿子节点标识 }; template<class Typew,class Typep> class HeapNode { friend Knap<Typew,Typep>; public: operator Typep() const { return uprofit; } private: Typep uprofit, //节点的价值上界 profit; //节点所相应的价值 Typew weight; //节点所相应的重量 int level; //活节点在子集树中所处的层序号 bbnode *ptr; //指向活节点在子集中相应节点的指针 }; template<class Typew,class Typep> class Knap { template<class Typew,class Typep> friend Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]); public: Typep MaxKnapsack(); private: MaxHeap<HeapNode<Typep,Typew>> *H; Typep Bound(int i); void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev); bbnode *E; //指向扩展节点的指针 Typew c; //背包容量 int n; //物品数 Typew *w; Typep *p; Typew cw; //物品重量数组 //物品价值数组 //当前重量

Typep cp; //当前价值 int *bestx; //最优解 }; template <class Type> inline void Swap(Type &a,Type &b); template<class Type> void BubbleSort(Type a[],int n); int main() { int n = 3;//物品数 int c = 30;//背包容量 int p[] = {0,45,25,25};//物品价值 下标从 1 开始 int w[] = {0,16,15,15};//物品重量 下标从 1 开始 int bestx[4];//最优解 cout<<"背包容量为:"<<c<<endl; cout<<"物品重量和价值分别为:"<<endl; for(int i=1; i<=n; i++) { cout<<"("<<w[i]<<","<<p[i]<<") "; } cout<<endl; cout<<"背包能装下的最大价值为:"<<Knapsack(p,w,c,n,bestx)<<endl; cout<<"此背包问题最优解为:"<<endl; for(int i=1; i<=n; i++) { cout<<bestx[i]<<" "; } cout<<endl; return 0; } template<class Typew,class Typep> Typep Knap<Typew,Typep>::Bound(int i)//计算节点所相应价值的上界 { Typew cleft = c-cw; //剩余容量高 Typep b = cp; //价值上界 //以物品单位重量价值递减序装填剩余容量 while(i<=n && w[i]<=cleft) { cleft -= w[i]; b += p[i]; i++;

} //装填剩余容量装满背包 if(i<=n) { b += p[i]/w[i]*cleft; } return b; } //将一个活节点插入到子集树和优先队列中 template<class Typew,class Typep> void Knap<Typew,Typep>::AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev) { bbnode *b = new bbnode; b->parent = E; b->LChild = ch; HeapNode<Typep,Typew> N; N.uprofit = up; N.profit = cp; N.weight = cw; N.level = lev; N.ptr = b; H->Insert(N); } //优先队列式分支限界法,返回最大价值,bestx 返回最优解 template<class Typew,class Typep> Typep Knap<Typew,Typep>::MaxKnapsack() { H = new MaxHeap<HeapNode<Typep,Typew>>(1000); //为 bestx 分配存储空间 bestx = new int[n+1]; //初始化 int i = 1; E = 0; cw = cp = 0; Typep bestp = 0;//当前最优值 Typep up = Bound(1); //价值上界 //搜索子集空间树 while(i!=n+1)

{ //检查当前扩展节点的左儿子节点 Typew wt = cw + w[i]; if(wt <= c)//左儿子节点为可行节点 { if(cp+p[i]>bestp) { bestp = cp + p[i]; } AddLiveNode(up,cp+p[i],cw+w[i],true,i+1); } up = Bound(i+1); //检查当前扩展节点的右儿子节点 if(up>=bestp)//右子树可能含有最优解 { AddLiveNode(up,cp,cw,false,i+1); } //取下一扩展节点 HeapNode<Typep,Typew> N; H->DeleteMax(N); E = N.ptr; cw = N.weight; cp = N.profit; up = N.uprofit; i = N.level; } //构造当前最优解 for(int j=n; j>0; j--) { bestx[j] = E->LChild; E = E->parent; } return cp; } //返回最大价值,bestx 返回最优解 template<class Typew,class Typep> Typep Knapsack(Typep p[],Typew w[],Typew c,int n, int bestx[]) { //初始化 Typew W = 0; //装包物品重量 Typep P = 0; //装包物品价值

//定义依单位重量价值排序的物品数组 Object *Q = new Object[n]; for(int i=1; i<=n; i++) { //单位重量价值数组 Q[i-1].ID = i; Q[i-1].d = 1.0*p[i]/w[i]; P += p[i]; W += w[i]; } if(W<=c) { return P;//所有物品装包 } //依单位价值重量排序 BubbleSort(Q,n); //创建类 Knap 的数据成员 Knap<Typew,Typep> K; K.p = new Typep[n+1]; K.w = new Typew[n+1]; for(int i=1; i<=n; i++) { K.p[i] = p[Q[i-1].ID]; K.w[i] = w[Q[i-1].ID]; } K.cp = 0; K.cw = 0; K.c = c; K.n = n; //调用 MaxKnapsack 求问题的最优解 Typep bestp = K.MaxKnapsack(); for(int j=1; j<=n; j++) { bestx[Q[j-1].ID] = K.bestx[j]; } delete Q; delete []K.w; delete []K.p; delete []K.bestx; return bestp; } template<class Type> void BubbleSort(Type a[],int n)

{ //记录一次遍历中是否有元素的交换 bool exchange; for(int i=0; i<n-1;i++) { exchange = false ; for(int j=i+1; j<=n-1; j++) { if(a[j]<=a[j-1]) { Swap(a[j],a[j-1]); exchange = true; } } //如果这次遍历没有元素的交换,那么排序结束 if(false == exchange) { break ; } } } template <class Type> inline void Swap(Type &a,Type &b) { Type temp = a; a = b; b = temp; } 四、程序运行结果:

五、分支限界法解决 0-1 背包问题复杂度分析: 时间复杂度为:O(2^n);空间复杂度:O(n2^n)。

六、回溯法与分支限界法分析比较: 这两种算法都得到了验证, 运行结果证明了算法设计是可行的。 通过对 O-1 背包问题的 算法设计及时间复杂度分析可以看出: 无论采用回溯法还是分支限界法, 都是在已知约束条 件下求解最大值建立数学模型算法实现的过程; 但算法具体实现和数据结构的建立要用到递 归和栈操作。比较回溯法和分支限界法,前者的时间复杂度高于后者,从耗费上而言优于后 者。对于回溯法,能够获得最优解,时间复杂度较高,判断右子树时,按效率密度 vi/wi 对剩余对象排序;对于分支限界法:速度较快,易求解,不过占用的内存较大,效率不高。

成 绩 单

评 语

成绩


相关文章:
回溯法和分支限界法解决0-1背包题(精).doc
回溯法和分支限界法解决0-1背包题(精)_其它_职业教育_教育专区。回溯法和分支限界法解决0-1背包题(精) 0-1 背包问题 计科 1 班 朱润华 2012040732 方法 1...
回溯法和分支限界法解决0-1背包题.doc
回溯法和分支限界法解决0-1背包题_计算机软件及应用_IT/计算机_专业资料。用回溯法和分支限界法解决0-1背包题,并对两种算法进行分析比较。...
分别用回溯法和分支限界法求解0-1背包问题.doc
分别用回溯法和分支限界法求解0-1背包问题_IT/计算机_专业资料。分别用回溯法和分支限界法求解0-1背包问题华北水利水电学院 2009 ~2010 班级: 一、 实验题目: ...
回溯法和分支限界法解决0-1背包题要点.doc
回溯法和分支限界法解决0-1背包题要点_其它_职业教育_教育专区。0-1 背包问
用回溯法和队列式分支限界算法求解0-1背包问题.doc
回溯法和队列式分支限界算法求解0-1背包问题 - 华北水利水电学院 2009 ~2010 学年 第 班级: 一、 实验题目: 200915326 数据结构与算法分析 实验报告 1 学期...
回溯法、分支限界法解0-1背包问题(计算机算法设计与分....doc
回溯法分支限界法0-1背包问题(计算机算法设计分析实验报告) - 报告中附
回溯法求0-1背包问题.doc
回溯法0-1背包问题 - 《算法设计分析》实验报告 学日号: 期: 姓得名: 分: 一、实验内容: 用回溯法求解 0/1 背包问题 注:给定 n 种物品和一个容量...
算法设计与分析复习题目及答案.doc
不能解决的问题:N 皇后问题,0/1 背包问题 是贪心算法的基本要素的是(贪心选择...回溯算法和分支限界法的问题的解空间树不会是( 无序树 14.哈弗曼编码的贪心...
回溯法在0_1背包问题中的应用.pdf
环境下验证了回溯法可以有效地解决 0-1 背包问题 ...而限界函数可以大大减少所生成的结点个数 , 避免...回溯法虽然是通过搜索问题的解空间来得到问 题的解...
用回溯法解决0-1背包问题.doc
用回溯法解决0-1背包问题_工学_高等教育_教育专区。算法试验报告,用回溯法解决...分别用回溯法和分支限界... 8页 2下载券 喜欢此文档的还喜欢 算法...
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题.doc
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题 - 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注:0/1 背包...
动态规划解决算法0-1背包问题实验报告(含源代码).doc
2.掌握动态规划、贪心算法、回溯法分支限界法的原理,并能够按其原理 编程实现...分析题 31 中算法的计算时间减至 O(nlogn) 3.给定 n 种物品和一背包...
动态规划与回溯法解决0-1背包问题.doc
动态规划与回溯法解决0-1背包问题 - 0-1 背包动态规划解决问题 一、问题描
解0-1背包问题的算法比较.pdf
课程设计 课程名称 题目名称 学生学院 专业班级 学号 算法分析与设计 0 1 背包...要有最优解性 质,故 0-1 背包问题满足动态规划、回溯法和分支限界法的求解...
分支界限法解0-1背包问题实验报告.doc
cout<<"|***分支限界法0-1 背包问题***| "<<endl; cout<<endl; cout...(); return 0; } 四 、运行结果 五 、实验小结回溯法的求解目标是找出解...
0_1背包问题的多种解法.doc
vi xi , i ?2 i ?2 i ?1 n n n 题比 ...(b)用回溯法求解 0-1 背包问题的过程 递归法:在...在分支限界法中用到的类 Knap 0-1 背包问题...
优先队列式分支限界法求解0-1背包问题_图文.doc
优先队列式分支限界法求解0-1背包问题 - 算法分析设计实验报告 第 7 次实验 姓名 时间 实验名称 6.4 上午 学号 地点 四合院 班级 优先队列式分支限界法求解 ...
0. 1背包问题的多种解法.doc
(b)用回溯法求解 0-1 背包问题的过程 递归法:在利用递归法解决 0-1 背包...限界分支法:在解 0-1 背包问题的优先队列式界限分支法中,活结点优先队列中...
算法分析复习题目及答案.doc
A、贪心法 B、动态规划法 C、分治策略 D、回溯法 42.0-1 背包问题的回溯...14、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序...
算法设计与分析复习题目及答案.doc
( A、贪心法 B、动态规划法 C、分治策略 A 42.0-1 背包问题的回溯算法所...A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 65...
更多相关标签: