图6-1
为了让偷窃的商品价值最高，你该选择哪些商品？
初始的状态是（6，0），表示背包容量为6磅，背包内物品总价值为0美元。接下来，我们要开始做选择了。每加一件物品，有两种选择，选或者不选。选择一个物品时，背包的容量会减少，里面的物品总价值会增加。背包问题变成了决策树，如图6-1所示。
图6-2
子树叶蓝色标记是按照回溯法枚举的选取物品的剩余容量和总价值，红色标记是能偷窃的商品的最高价值4200美元。
小结：优化方法：
剪枝一：当重量大于背包的容量时，没有必要对剩下的物品进行决策；
剪枝二：将剩下的所有物品都选取，其总价值也没有目前所求得的总价值还大的话，就可以返回。
回溯法枚举所有的解空间，时间复杂度是O(2ⁿ)。
3、动态规划法
与回溯法同样的例子，假设你是一个小偷，背着一个可装下6磅东西的背包，你可以偷窃的商品如下：
图6-3
为了让偷窃的商品价值最高，你该选择哪些商品？
第1步，我们从一个网格开始，将背包问题网格化。网格的行对应的是商品，列对应的是不同容量(1~6磅)的背包。如图6-4所示。
图6-4
第2步，我们先来一步一步做。首先来看第1行，加入2磅的吉他。第1个单元格表示背包的的容量为1磅。吉他的重量是2磅，这意味着它不能装入背包！第1行的其它单元格的背包的容量≥2磅，可以装入吉他，总价值是1500美元。如图6-5所示。
