假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。

正确答案:贪心算法：
（1）标准：重量、价值和单位价值。
（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。
使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。
使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。
（3）显然使用单位价值作为标准得到的是最优解。
回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：


在Q₁处获得该问题的最优解为（1，1，1，1，0，0，1），背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。