首页 > 代码库 > 回溯法--0-1背包问题
回溯法--0-1背包问题
算法描述：
0-1背包的回溯法，与装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树进行搜索。否则将右子树剪去。
计算右子树上界的更好算法是：
将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。
算法实现：
由Bound函数计算当前节点处的上界。
类Knap的数据成员记录解空间树的节点信息，以减少参数传递及递归调用所需的栈空间。
在解空间树的当前扩展结点处，仅当要进入右子树时，才计算上界bound，以判断是否可将右子树剪去。
进入左子树时不需要计算上界，因为它与其父节点的上界相同。
算法实现：（代码有点小问题，正在修改中）
#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace std;template <class Typew,class Typep>class Knap{ 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>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]*cleft/w[i]; return b;}class Object{ friend int Knapsack(int *,int *,int,int);public: int operator <= (Object a)const { return (d >= a.d); }private: int ID; float d;};int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b );}template <class Typew,class Typep>Typep Knapsack(Typep p[],Typew w[],Typew c,int n){ int i; //初始化 int W = 0; int P = 0; Object* Q = new Object[n]; for(i=0;i<n;i++) { // cout<<p[i]<<" "<<w[i]<<endl<<"-------------------------"<<endl; Q[i].ID = i; Q[i].d = 1.0*p[i]/w[i]; // cout<<Q[i].ID<<" "<<Q[i].d<<endl<<"----------------------"<<endl; P += p[i]; W += w[i]; // cout<<P<<" "<<W<<endl<<endl; } if(W<=c) return P;//装入所有物品 //依物品单位重量价值排序 qsort (Q,n, sizeof(int), compare); Knap<Typew,Typep> K; K.p = new Typep [n+1]; K.w = new Typew [n+1]; for(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.n = n; K.bestp = 0; K.Backtrack(1);// cout<<K.bestp<<endl; delete [] Q; delete [] K.w; delete [] K.p; return K.bestp;}int main(){ int p[4] = {9,10,7,4}; int w[4]= {3,5,2,1}; int num = Knapsack(p,w,7,4); cout<<num<<endl; return 0;}回溯法--0-1背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。