欢迎来到天天文库
浏览记录
ID:5806099
大小:49.50 KB
页数:2页
时间:2017-12-25
《(原创精品)n=3时的0-1背包问题(回溯法)》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、用回溯法解决3种可选择物品的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)}n=3时的0-1背包问题:w=[16,15,15]p=[45,25,25]c=30开始时,Cr=C=30,V=0,A为唯一活结点,也是当前扩展结点扩展A,先到达B结点Cr=Cr-w1=14,V=V+v1=45此时A、B为活结点,B成为当前扩展结点扩展B,先到达DCr2、、E是活结点,E成为新的扩展结点扩展E,先到达JCr3、且50>45,皆得到一个可行解x=(0,1,1),V=50L不可扩展,成为死结点,返回到F再扩展F到达MM是叶结点,且25<50,不是最优解M不可扩展,成为死结点,返回到FF没有可扩展结点,成为死结点,返回到C再扩展C到达GCr=30,V=0,活结点为A、C、G,G为当前扩展结点扩展G,先到达N,N是叶结点,且25<50,不是最优解,又N不可扩展,返回到G再扩展G到达O,O是叶结点,且0<50,不是最优解,又O不可扩展,返回到GG没有可扩展结点,成为死结点,返回到CC没有可扩展结点,成为死结点,返回到AA没有可扩展结点,4、成为死结点,算法结束,最优解X=(0,1,1),最优值V=50
2、、E是活结点,E成为新的扩展结点扩展E,先到达JCr3、且50>45,皆得到一个可行解x=(0,1,1),V=50L不可扩展,成为死结点,返回到F再扩展F到达MM是叶结点,且25<50,不是最优解M不可扩展,成为死结点,返回到FF没有可扩展结点,成为死结点,返回到C再扩展C到达GCr=30,V=0,活结点为A、C、G,G为当前扩展结点扩展G,先到达N,N是叶结点,且25<50,不是最优解,又N不可扩展,返回到G再扩展G到达O,O是叶结点,且0<50,不是最优解,又O不可扩展,返回到GG没有可扩展结点,成为死结点,返回到CC没有可扩展结点,成为死结点,返回到AA没有可扩展结点,4、成为死结点,算法结束,最优解X=(0,1,1),最优值V=50
3、且50>45,皆得到一个可行解x=(0,1,1),V=50L不可扩展,成为死结点,返回到F再扩展F到达MM是叶结点,且25<50,不是最优解M不可扩展,成为死结点,返回到FF没有可扩展结点,成为死结点,返回到C再扩展C到达GCr=30,V=0,活结点为A、C、G,G为当前扩展结点扩展G,先到达N,N是叶结点,且25<50,不是最优解,又N不可扩展,返回到G再扩展G到达O,O是叶结点,且0<50,不是最优解,又O不可扩展,返回到GG没有可扩展结点,成为死结点,返回到CC没有可扩展结点,成为死结点,返回到AA没有可扩展结点,
4、成为死结点,算法结束,最优解X=(0,1,1),最优值V=50
此文档下载收益归作者所有