2. 用回溯法求解0-1背包问题。算法设计思路 伪代码

算法设计思路：
1. 从第一个物品开始，选择装或不装入背包。
2. 若装入该物品不超重，则考虑下一个物品是否装入。
3. 若下一个物品装入背包后不超重，则继续考虑下一个物品是否装入。
4. 直到考虑完所有的物品，或者当前背包已经装满。
5. 回溯到上一个状态，考虑不装入当前物品的情况，继续考虑下一个物品。
6. 直到回溯到初始状态，或者所有状态都已经遍历完毕。

伪代码：

def backtrack(k, cw, items, n, w, bestV):
# k表示当前考虑到第几个物品
# cw表示当前背包中的物品总重量
# items表示每个物品的重量和价值，二维数组
# n表示物品的个数
# w表示背包能承受的最大重量
# bestV表示当前最优解的价值

if k == n: # 物品考虑完毕
if cw <= w and bestV < cv: # 更新最优解
bestV = cv
return

# 不装入第k个物品
backtrack(k + 1, cw, items, n, w, bestV)

# 装入第k个物品
if cw + items[k][0] <= w: # 如果不超重
cv += items[k][1] # 更新当前总价值
backtrack(k + 1, cw + items[k][0], items, n, w, bestV)
cv -= items[k][1] # 回溯状态，恢复原来的总价值