(原创精品)n=3时的0-1背包问题(回溯法)

《(原创精品)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，先到达DCr

2、、E是活结点，E成为新的扩展结点扩展E，先到达JCr

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