用回溯法解0_1背包问题时,会用到状态空间树。在搜索状态空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索,否则将右子树剪去。设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r≤bestp时,可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界,用此值来剪枝。为了便于计算上界,可先将物品依其单位重量价值从大到小排序,此后只要顺序考察各物品即可。在实现时,由MaxBoundary函数计算当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录了解