回溯法和分支限界法解决01背包题精.docx

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},?∑wixi≤c,且∑vixi达最大.即一个特殊的整数规划问题。
二、回溯法步骤思想描述：
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>
usingnamespacestd;
template<classTypew,classTypep>
classKnap
{
template<classTypew,classTypep>
friendTypepKnapsack(Typep[],Typew[],Typew,int);
private:
TypepBound(inti);
voidBacktrack(inti);
Typewc;//背包容量
intn;//物品数
Typew*w;//物品重量数组
Typep*p;//物品价值数组
Typewcw;//当前重量
Typepcp;//当前价值
Typepbestp;//当前最后价值
};
template<classTypew,classTypep>
TypepKnapsack(Typepp[],Typeww[],Typewc,intn);
template<classType>
inlinevoidSwap(Type&a,Type&b);
template<classType>
voidBubbleSort(Typea[],intn);
intmain()
{
intn=4;//物品数
intc=7;//背包容量
intp[]={0,9,10,7,4};//物品价值下标从1开始
intw[]={0,3,5,2,1};//物品重量下标从1开始
cout<<"背包容量为："<<c<<endl;
cout<<"物品重量和价值分别为："<<endl;
for(inti=1;i<=n;i++)
{
cout<<"("<<w[i]<<","<<p[i]<<")";
}
cout<<endl;
cout<<"背包能装下的最大价值为："<<Knapsack(p,w,c,n)<<endl;return0;
}
template<classTypew,classTypep>
voidKnap<Typew,Typep>::Backtrack(inti)
{
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