(原创精品)0-1背包问题(回溯法)

《(原创精品)0-1背包问题(回溯法)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、0-1背包问题0-1背包问题的解空间可用子集树表示在搜索解空间树时，只要其左儿子结点是一个可行结点——>搜索进入其左子树当右子树中有可能包含最优解——>进入右子树搜索否则将右子树减去r——当前剩余物品价值总和cp——当前价值bestp——当前最优价值当cp+r≤bestp时，可减去右子树计算右子树中解的上界的更好的方法①将剩余物品依其单位价值排序②依次装入物品，直至装不下时③再装入该物品的一部分而装满背包④由此得到的价值——右子树中解的上界0-1背包问题的一个实例已知：n=4c=7p=[91074]w=[3521]解：①这四个物品的单位价值分别——[323.54]②以物品单位重量价值的递减序

2、装入物品③先装物品4④装入物品3和物品1⑤装入这3个物品后，剩余的背包容量为1{7-（3+2+1）}只能装入0.2{1/5}的物品2⑥得到一个解——x=[10.211]相应的价值为22{1*9+0.2*10+1*7+1*4}⑦这不是一个可行解，但其价值是最优值的上界算法分析：①Bound计算当前结点处的上界②Knap的数据成员记录解空间树中的结点信息以减少参数传递及递归调用所需的栈空间①在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界Bound，以判断是否可将右子树减去④进入左子树时不需计算上界，因为其上界与其父结点的上界相同核心代码：temp

3、ep>classKnap{friendTypepKnapsack(Typep*,Typew*,Typew,int);private:TypepBound(inti);VoidBacktrack(inti);Typew*w;Typep*p;Typewcw;Typepcp;Typepbestp;};TempvoidKnap::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-=

4、p[i];}templateTypepKnap::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}