..
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 \#include
template
template
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
Typep Knapsack(Typep p[],Typew w[],Typew c,int n); template
inline void Swap(Type &a,Type &b); template
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<<\背包容量为:\
cout<<\物品重量和价值分别为:\ for(int i=1; i<=n; i++) {
cout<<\ }
cout< cout<<\背包能装下的最大价值为:\ return 0; } template void Knap 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 Typep Knap 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 friend Typep Knapsack(Typep[],Typew [],Typew,int); public: int operator <= (Object a)const { return (d>=a.d); } private: int ID; float d; ;.