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

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

ID:5806166

大小:47.50 KB

页数:3页

时间:2017-12-25

(原创精品)0-1背包问题(回溯法)_第1页
(原创精品)0-1背包问题(回溯法)_第2页
(原创精品)0-1背包问题(回溯法)_第3页
资源描述:

《(原创精品)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;}

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。