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

回溯法和分支限界法解决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背包问题
分别用回溯法和分支限界法求解0-1背包问题_IT/计算机_专业资料。分别用回溯法和分支限界法求解0-1背包问题华北水利水电学院 2009 ~2010 班级: 一、 实验题目: ...
回溯法、分支限界法解0-1背包问题(计算机算法设计...
回溯法分支限界法0-1背包问题(计算机算法设计分析实验报告) - 报告中附有可直接运行代码和实验结果截图(西大学子)。 编程语言:java 开发工具:eclipse 3.4...
第五组分支限界法(0-1背包问题)
第五组分支限界法(0-1背包问题) - 实训一 背包问题的分支限界法与实现 问题的分支限界法 0-1 背包问题的分支限界法与实现 任务分 配 成员 1 成员 2 张藤...
优先队列式分支限界法求解0-1背包问题_图文
优先队列式分支限界法求解0-1背包问题 - 算法分析设计实验报告 第 7 次实验 姓名 时间 实验名称 6.4 上午 学号 地点 四合院 班级 优先队列式分支限界法求解 ...
0036算法笔记——【分支限界法】0-1背包问题
0036算法笔记——【分支限界法】0-1背包问题_计算机软件及应用_IT/计算机_专业...回溯法和分支限界法解决... 14页 3下载券 分支限界法实现0-1背包 5页 免费...
分支界限法解0-1背包问题实验报告
cout&lt;&lt;&quot;|***分支限界法0-1 背包问题***| &quot;&lt;&lt;endl; cout&lt;&lt;endl; cout...(); return 0; } 四 、运行结果 五 、实验小结回溯法的求解目标是找出解...
实验4 用分支限界法实现0-1背包问题
实验四 用分支限界法实现 0-1 背包问题 一.实验目的 1.熟悉分支限界法的基本...用分支限界求解0-1背包问... 6页 1下载券 分别用回溯法和分支限界... ...
分支界限法解0-1背包问题实验报告
cout&lt;&lt;&quot;|***分支限界法0-1 背包问题***| &quot;&lt;&lt;endl; cout&lt;&lt;endl; cout...(); return 0; } 四 、运行结果 实验小结 五 、实验小结回溯法的求解目标...
0-1背包问题(分支限界法)
0-1背包问题(分支限界法) - 分支限界法——01 背包问题 12 软工 一、 问题描述 0-1 背包问题: 给定 n 种物品一个背包。 物品 i 的重量是 Wi, 其...
分支限界法求0-1背包问题实验程序以及代码(C++)
分支限界法0-1背包问题实验程序以及代码(C++)_理学_高等教育_教育专区。分支...回溯法分支限界法解0-... 15页 1下载券 喜欢此文档的还喜欢 分支...
更多相关标签: