0-1背包问题背包问题(动规回溯分支限界法贪心)

2023年7月31日发(作者：)

0-1背包问题背包问题（动规回溯分⽀限界法贪⼼）写在前⾯：仅为个⼈代码/总结，未必标准，仅供参考！如有错误，还望指出交流，共同进步！（⼀）0-1背包问题【动态规划法】⼀、算法思路0-1背包问题具有最优⼦结构性质和重叠⼦问题性质。⾸先定义m(i,j)：从物品i、i+1、…、n-1、n中选择物品装⼊容量⼤⼩为j的背包，使该背包的总价值最⼤，最⼤值为m(i,j)，即最优值。假设背包容量为c，物品总数n，物品i的重量表⽰wi，价值表⽰vi，于是0-1背包问题的最优值为m(1,c)。计算m(1,c)的值之前，先递归地定义最优值的计算⽅法：（1）当背包剩余容量为j时，且j≥wi, m(i,j)= max{ m(i+1,j), m(i+1,j-wi)+vi)}。即当此时的背包剩余容量⼤于物品i的重量，于是在选取物品i和不选取物品i之中选择较⼤者。（2）当背包剩余容量为j时，且0using namespace std;void getData(int* a,int* b,int n){ srand(time(0)); for(int i=1;i<=n;i++) { a[i]=rand()%15+1; } for(int i=1;i<=n;i++) { b[i]=rand()%15+1; }}void Knapsack(int* v,int* w, int c, int n,int (*m)[21]){ int jMax=min(w[n]-1,c);//⾸先处理第n个物品 for(int j=0;j<=jMax;j++)//剩余容量＜物品n重量 { m[n][j] = 0; } for(int j=w[n];j<=c;j++)//剩余容量≥物品n重量 { m[n][j] = v[n]; } for(int i=n-1;i>1;i--) { jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++)//当背包剩余容量为j时，且0=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}void Traceback(int (*m)[21], int* w, int c, int n,int* x){ for(int i=1;iusing namespace std;class Knap{ friend int Knapsack(int*,int*,int,int,int[]);private: int Bound(int i); void Backtrack(int i); int c; int n; int *x; int *bestx; int *w; int *p; int cw; int cp; int bestp;};class Object{ friend int Knapsack(int*,int*,int,int,int*);public: int ID; float d;};bool cmp(Object A,Object B){ return A.d>B.d;}int Knap::Bound(int i){ int cleft=c-cw; int 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;}void Knap::Backtrack(int i){ if(i>n)//到达叶结点 { for(int j=1;j<=n;j++) { bestx[j]=x[j]; } bestp=cp; return; } if(cw+w[i]<=c)//进⼊左⼦树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; x[i]=0; } if(Bound(i+1)>bestp)//进⼊右⼦树 Backtrack(i+1);}int Knapsack(int* p,int * w,int c,int n,int* bestx){ int W=0; int P=0; Object *Q=new Object[n]; for(int i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=10*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) return P; sort(Q+1,Q+n+1,cmp); Knap K; K.p=new int[n+1]; K.w=new int[n+1]; K.x=new int[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.x[i]=0; } =0; =0; K.c=c; K.n=n; =0; =bestx; ack(1); for(int i=1;i<=n;i++) { K.x[i]=[i]; } for(int i=1;i<=n;i++) { [Q[i-1].ID]=K.x[i]; } delete []Q; delete []K.w; delete []K.p; delete []K.x; return ;}int main(){ int n,c; cin>>n>>c; int *p,*w,*bestx; p=new int[n+1]; w=new int[n+1]; bestx=new int[n+1]; for(int i=1;i<=n;i++) { cin>>w[i]; } for(int i=1;i<=n;i++) { cin>>p[i]; bestx[i]=0; } int res=Knapsack(p,w,c,n,bestx); cout<n)//到达叶结点 { ii=n; bestp=cp; return; } if(cw+w[i]<=c)//进⼊左⼦树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); if(ii==i) {bestx[i]=1;ii--;} cw-=w[i]; cp-=p[i]; x[i]=0; } if(Bound(i+1)>bestp)//进⼊右⼦树 { Backtrack(i+1); if(ii==i) {bestx[i]=0;ii--;} }}【优先队列式分⽀限界法】⼀、算法思想分⽀限界法常以⼴度优先或最⼩耗费优先（最⼤效益优先）⽅式搜索问题的解空间树， 0-1背包问题的解空间树是⼀个颗⼦集树。对于0-1背包问题中的每个活结点只有两个⼉⼦结点，分别表⽰选取和不选取物品i；在判断⼉⼦结点是否能加⼊到活结点表中，有两个函数条件需要满⾜，⼀个是约束函数，判断能否满⾜背包容量约束，另⼀个是限界函数，判断是否可能有最优解。为了尽快找到0-1背包问题的解，每次选取下⼀个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下⼀个结点。因此，每次选择扩展结点的⽅法：当前情况下，在活结点表中选择活结点的上界uprofit（通过限界函数Bound求出）最⼤的活结点成为当前的扩展结点，即以uprofit为优先级将活结点插⼊到优先队列中，每⼀次选取优先级最⾼的结点作为当前拓展结点。 这⼀过程⼀直持续到找到所需的解或活结点表为空时为⽌。为了在活结点表中选择拥有最⼤的上界uprofit的活结点，在活结点表上实现优先队列。⼆、算法步骤⾸先，根据每个物品的重量和价值计算出物品的单价，根据单价将物品进⾏排序，以下是优先队列式分⽀限界法的搜索过程：①搜索解空间建⽴⼆叉树，从根结点开始。②⼴度优先搜索⼆叉树，并⽤upfrofit表⽰活结点的优先级构建最⼤堆。③选取优先级最⾼的活结点作为扩展结点，找出可⾏解。④检查左⼉⼦结点是否是可⾏结点（即上界⼤于当前最优值且加上该物品的重量不超过背包容量），如果是则将它加⼊到活结点优先队列中，⽽当前扩展结点的右⼉⼦⼀定是可⾏结点，仅当右⼉⼦满⾜上界约束时才将它加⼊到活结点优先队列中。⑤维护堆结构，使得堆顶元素依然是优先级最⾼的结点。（构建优先队列可直接调⽤C++STL库中的priority_queue，插⼊活结点⾃动维护）⑥重复③④⑤步骤直到优先队列为空。三、实现代码#include using namespace std;typedef int Typew;typedef int Typep;//物品类class Object{ friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);public: int operator <= (Object a) const{ return (d >= a.d); }private: int ID; //物品编号 float d; //单位重量价值};//树结点类class bbnode{ friend class Knap; friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);private: bbnode *parent; //指向⽗节点的指针 int LChild; //左⼉⼦结点标记};//堆结点类class HeapNode{ friend class Knap; friend class MaxHeap;public: operator Typep()const{return uprofit;};private: Typep uprofit, //结点的价值上界 profit; //结点所相应的价值 Typew weight; //结点所相应的重量 int level; //活结点在⼦集树中所处的层序号 bbnode *elemPtr; //指向该活结点在⼦集树中相应结点的指针};//0-1背包问题的主类class Knap{class Knap{ friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);public: Typep MaxKnapsack();private: priority_queue H; //限界函数：计算结点价值上界 Typep Bound(int i); //将活结点插⼊⼦集树和优先队列中 void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; //指向扩展结点的指针 Typew c; //背包容量 int n; //物品总数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前装包重量 Typep cp; //当前装包价值 int *bestx; //最优解};Typep Knap::MaxKnapsack(){ bestx = new int [n+1]; int i = 1; //⽣成⼦集树中的第⼀层的结点 E = 0;

cw = 0; cp = 0; Typep bestp = 0; //当前最优值 Typep up = Bound(1); //

选取物品1之后的价值上界 //当选择左⼉⼦结点时，考虑约束函数 //当选择右⼉⼦结点时，考虑限界函数 while (i != n+1) { //检查当前扩展结点的左⼉⼦结点 Typew wt = cw + w[i]; //当前选择物品i之后的总重量wt if(wt <= c) //左⼉⼦结点可⾏ { if(cp + p[i] > bestp) bestp = cp + p[i]; AddLiveNode(up, cp + p[i], cw + w[i], 1, i); } //检查当前扩展结点的右⼉⼦结点 up = Bound(i + 1); //未选择物品i之后的价值上界 if(up >= bestp) AddLiveNode(up, cp, cw, 0, i); //从优先队列中选择uprofit最⼤的结点成为扩展结点 HeapNode N; N=(); (); E = r; cw = ; cp = ; up = t; i = + 1;

} //从⼦集树中的某叶⼦结点开始构造当前最优解 for (int i = n; i > 0; i--) { bestx[i] = E->LChild; E = E->parent; } return cp;}Typep Knap::Bound(int i){ Typew cleft = c - cw; 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;}void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level){ bbnode *b=new bbnode; b->parent=E; b->LChild=ch; HeapNode N; t=up; =cp; =cw; =level; r=b; (N);}Typep Knapsack(Typew *w, Typep *p, 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) { for(int i =1; i<=n; i++) { bestx[i] = p[i]; } return P; } //采⽤简单冒泡排序，对物品以单位重量价值降序排序 for(int i = 1; i>N>>c; for(int i=1;i<=N;i++) { cin>>w[i]>>p[i]; } bestp = Knapsack(w, p, c, N, bestx); for(int i = 1; i <= N; i++) { if(i ==1 ) cout<<"解向量："; cout<using namespace std;struct object{ int num; float value; float weight; float flag;};};bool cmp1(object A,object B){ float u=,v=; return (*u)>(*v);}bool cmp2(object A,object B){ return <;}float Knapsack(object* O,float c,int n){ float curweight=0,curvalue=0; for(int i=0;i0) { O[i].flag=(c-curweight)/O[i].weight; curvalue+=O[i].flag*O[i].value; curweight=c; } else { O[i].flag=0; } } return curvalue;}void Traceback(object* O,int n){ for(int i=0;i>n; object O[n]; for(int i=0;i>O[i].weight>>O[i].value; O[i].num=i+1; } cout<<"请输⼊背包的容量:"; float c; cin>>c; sort(O,O+n,cmp1); float res=Knapsack(O,c,n); cout<

{ for(int j=w[i];j<=c;j++)

{ m[j] = max(m[j], m[j - w[i]] + v[i]); }}⼆、多重背包问题：限定每⼀种物品的个数，解决多重背包问题可将其转化为0-1背包问题求解。

2023年7月31日发(作者：)

0-1背包问题背包问题（动规回溯分⽀限界法贪⼼）写在前⾯：仅为个⼈代码/总结，未必标准，仅供参考！如有错误，还望指出交流，共同进步！（⼀）0-1背包问题【动态规划法】⼀、算法思路0-1背包问题具有最优⼦结构性质和重叠⼦问题性质。⾸先定义m(i,j)：从物品i、i+1、…、n-1、n中选择物品装⼊容量⼤⼩为j的背包，使该背包的总价值最⼤，最⼤值为m(i,j)，即最优值。假设背包容量为c，物品总数n，物品i的重量表⽰wi，价值表⽰vi，于是0-1背包问题的最优值为m(1,c)。计算m(1,c)的值之前，先递归地定义最优值的计算⽅法：（1）当背包剩余容量为j时，且j≥wi, m(i,j)= max{ m(i+1,j), m(i+1,j-wi)+vi)}。即当此时的背包剩余容量⼤于物品i的重量，于是在选取物品i和不选取物品i之中选择较⼤者。（2）当背包剩余容量为j时，且0using namespace std;void getData(int* a,int* b,int n){ srand(time(0)); for(int i=1;i<=n;i++) { a[i]=rand()%15+1; } for(int i=1;i<=n;i++) { b[i]=rand()%15+1; }}void Knapsack(int* v,int* w, int c, int n,int (*m)[21]){ int jMax=min(w[n]-1,c);//⾸先处理第n个物品 for(int j=0;j<=jMax;j++)//剩余容量＜物品n重量 { m[n][j] = 0; } for(int j=w[n];j<=c;j++)//剩余容量≥物品n重量 { m[n][j] = v[n]; } for(int i=n-1;i>1;i--) { jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++)//当背包剩余容量为j时，且0=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}void Traceback(int (*m)[21], int* w, int c, int n,int* x){ for(int i=1;iusing namespace std;class Knap{ friend int Knapsack(int*,int*,int,int,int[]);private: int Bound(int i); void Backtrack(int i); int c; int n; int *x; int *bestx; int *w; int *p; int cw; int cp; int bestp;};class Object{ friend int Knapsack(int*,int*,int,int,int*);public: int ID; float d;};bool cmp(Object A,Object B){ return A.d>B.d;}int Knap::Bound(int i){ int cleft=c-cw; int 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;}void Knap::Backtrack(int i){ if(i>n)//到达叶结点 { for(int j=1;j<=n;j++) { bestx[j]=x[j]; } bestp=cp; return; } if(cw+w[i]<=c)//进⼊左⼦树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i]; x[i]=0; } if(Bound(i+1)>bestp)//进⼊右⼦树 Backtrack(i+1);}int Knapsack(int* p,int * w,int c,int n,int* bestx){ int W=0; int P=0; Object *Q=new Object[n]; for(int i=1;i<=n;i++) { Q[i-1].ID=i; Q[i-1].d=10*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) return P; sort(Q+1,Q+n+1,cmp); Knap K; K.p=new int[n+1]; K.w=new int[n+1]; K.x=new int[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.x[i]=0; } =0; =0; K.c=c; K.n=n; =0; =bestx; ack(1); for(int i=1;i<=n;i++) { K.x[i]=[i]; } for(int i=1;i<=n;i++) { [Q[i-1].ID]=K.x[i]; } delete []Q; delete []K.w; delete []K.p; delete []K.x; return ;}int main(){ int n,c; cin>>n>>c; int *p,*w,*bestx; p=new int[n+1]; w=new int[n+1]; bestx=new int[n+1]; for(int i=1;i<=n;i++) { cin>>w[i]; } for(int i=1;i<=n;i++) { cin>>p[i]; bestx[i]=0; } int res=Knapsack(p,w,c,n,bestx); cout<n)//到达叶结点 { ii=n; bestp=cp; return; } if(cw+w[i]<=c)//进⼊左⼦树 { x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); if(ii==i) {bestx[i]=1;ii--;} cw-=w[i]; cp-=p[i]; x[i]=0; } if(Bound(i+1)>bestp)//进⼊右⼦树 { Backtrack(i+1); if(ii==i) {bestx[i]=0;ii--;} }}【优先队列式分⽀限界法】⼀、算法思想分⽀限界法常以⼴度优先或最⼩耗费优先（最⼤效益优先）⽅式搜索问题的解空间树， 0-1背包问题的解空间树是⼀个颗⼦集树。对于0-1背包问题中的每个活结点只有两个⼉⼦结点，分别表⽰选取和不选取物品i；在判断⼉⼦结点是否能加⼊到活结点表中，有两个函数条件需要满⾜，⼀个是约束函数，判断能否满⾜背包容量约束，另⼀个是限界函数，判断是否可能有最优解。为了尽快找到0-1背包问题的解，每次选取下⼀个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下⼀个结点。因此，每次选择扩展结点的⽅法：当前情况下，在活结点表中选择活结点的上界uprofit（通过限界函数Bound求出）最⼤的活结点成为当前的扩展结点，即以uprofit为优先级将活结点插⼊到优先队列中，每⼀次选取优先级最⾼的结点作为当前拓展结点。 这⼀过程⼀直持续到找到所需的解或活结点表为空时为⽌。为了在活结点表中选择拥有最⼤的上界uprofit的活结点，在活结点表上实现优先队列。⼆、算法步骤⾸先，根据每个物品的重量和价值计算出物品的单价，根据单价将物品进⾏排序，以下是优先队列式分⽀限界法的搜索过程：①搜索解空间建⽴⼆叉树，从根结点开始。②⼴度优先搜索⼆叉树，并⽤upfrofit表⽰活结点的优先级构建最⼤堆。③选取优先级最⾼的活结点作为扩展结点，找出可⾏解。④检查左⼉⼦结点是否是可⾏结点（即上界⼤于当前最优值且加上该物品的重量不超过背包容量），如果是则将它加⼊到活结点优先队列中，⽽当前扩展结点的右⼉⼦⼀定是可⾏结点，仅当右⼉⼦满⾜上界约束时才将它加⼊到活结点优先队列中。⑤维护堆结构，使得堆顶元素依然是优先级最⾼的结点。（构建优先队列可直接调⽤C++STL库中的priority_queue，插⼊活结点⾃动维护）⑥重复③④⑤步骤直到优先队列为空。三、实现代码#include using namespace std;typedef int Typew;typedef int Typep;//物品类class Object{ friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);public: int operator <= (Object a) const{ return (d >= a.d); }private: int ID; //物品编号 float d; //单位重量价值};//树结点类class bbnode{ friend class Knap; friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);private: bbnode *parent; //指向⽗节点的指针 int LChild; //左⼉⼦结点标记};//堆结点类class HeapNode{ friend class Knap; friend class MaxHeap;public: operator Typep()const{return uprofit;};private: Typep uprofit, //结点的价值上界 profit; //结点所相应的价值 Typew weight; //结点所相应的重量 int level; //活结点在⼦集树中所处的层序号 bbnode *elemPtr; //指向该活结点在⼦集树中相应结点的指针};//0-1背包问题的主类class Knap{class Knap{ friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);public: Typep MaxKnapsack();private: priority_queue H; //限界函数：计算结点价值上界 Typep Bound(int i); //将活结点插⼊⼦集树和优先队列中 void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; //指向扩展结点的指针 Typew c; //背包容量 int n; //物品总数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前装包重量 Typep cp; //当前装包价值 int *bestx; //最优解};Typep Knap::MaxKnapsack(){ bestx = new int [n+1]; int i = 1; //⽣成⼦集树中的第⼀层的结点 E = 0;

cw = 0; cp = 0; Typep bestp = 0; //当前最优值 Typep up = Bound(1); //

选取物品1之后的价值上界 //当选择左⼉⼦结点时，考虑约束函数 //当选择右⼉⼦结点时，考虑限界函数 while (i != n+1) { //检查当前扩展结点的左⼉⼦结点 Typew wt = cw + w[i]; //当前选择物品i之后的总重量wt if(wt <= c) //左⼉⼦结点可⾏ { if(cp + p[i] > bestp) bestp = cp + p[i]; AddLiveNode(up, cp + p[i], cw + w[i], 1, i); } //检查当前扩展结点的右⼉⼦结点 up = Bound(i + 1); //未选择物品i之后的价值上界 if(up >= bestp) AddLiveNode(up, cp, cw, 0, i); //从优先队列中选择uprofit最⼤的结点成为扩展结点 HeapNode N; N=(); (); E = r; cw = ; cp = ; up = t; i = + 1;

} //从⼦集树中的某叶⼦结点开始构造当前最优解 for (int i = n; i > 0; i--) { bestx[i] = E->LChild; E = E->parent; } return cp;}Typep Knap::Bound(int i){ Typew cleft = c - cw; 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;}void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level){ bbnode *b=new bbnode; b->parent=E; b->LChild=ch; HeapNode N; t=up; =cp; =cw; =level; r=b; (N);}Typep Knapsack(Typew *w, Typep *p, 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) { for(int i =1; i<=n; i++) { bestx[i] = p[i]; } return P; } //采⽤简单冒泡排序，对物品以单位重量价值降序排序 for(int i = 1; i>N>>c; for(int i=1;i<=N;i++) { cin>>w[i]>>p[i]; } bestp = Knapsack(w, p, c, N, bestx); for(int i = 1; i <= N; i++) { if(i ==1 ) cout<<"解向量："; cout<using namespace std;struct object{ int num; float value; float weight; float flag;};};bool cmp1(object A,object B){ float u=,v=; return (*u)>(*v);}bool cmp2(object A,object B){ return <;}float Knapsack(object* O,float c,int n){ float curweight=0,curvalue=0; for(int i=0;i0) { O[i].flag=(c-curweight)/O[i].weight; curvalue+=O[i].flag*O[i].value; curweight=c; } else { O[i].flag=0; } } return curvalue;}void Traceback(object* O,int n){ for(int i=0;i>n; object O[n]; for(int i=0;i>O[i].weight>>O[i].value; O[i].num=i+1; } cout<<"请输⼊背包的容量:"; float c; cin>>c; sort(O,O+n,cmp1); float res=Knapsack(O,c,n); cout<

{ for(int j=w[i];j<=c;j++)

{ m[j] = max(m[j], m[j - w[i]] + v[i]); }}⼆、多重背包问题：限定每⼀种物品的个数，解决多重背包问题可将其转化为0-1背包问题求解。