《n=3时的01背包问题.docx》由会员分享，可在线阅读，更多相关《n=3时的01背包问题.docx（2页珍藏版）》请在三一办公上搜索。
n=3时的01背包问题用回溯法解决3种可选择物品的0-1背包问题 当n=3时，其解空间是 ， 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，先到达D Crw2，D导致一个不可行解，回溯到B 再扩展B到达E E可行，此时A、B、E是活结点，E成为新的扩展结点 扩展E，先到达J Cr45，皆得到一个可行解x=(0,1,1)，V=50 L不可扩展，成为死结点，返回到F 再扩展F到达M M是叶结点，且2550，不是最优解 M不可扩展，成为死结点，返回到F F没有可扩展结点，成为死结点，返回到C 再扩展C到达G Cr=30，V=0，活结点为A、C、G，G为当前扩展结点 扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到G 再扩展G到达O，O是叶结点，且050，不是最优解，又O不可扩展，返回到G G没有可扩展结点，成为死结点，返回到C C没有可扩展结点，成为死结点，返回到A A没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值V=50
