0_1背包问题,回溯法解背包问题

0-l背包问题是子集选取问题。一般情况下，0-1背包问题是NP难题。0-1背包

问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类

似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当

右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余

物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右

子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后

依次装入物品，直至装不下时，再装入该物品的一