背包问题回溯法改进o2的n次方改进后的代码

背包问题是一个经典的动态规划问题，回溯法可以用来解决背包问题，但是回溯法的时间复杂度是指数级别的，需要通过一些优化来加速。

一种优化方式是使用记忆化搜索，即将已经计算过的状态保存下来，避免重复计算。另一种优化方式是使用剪枝，即在搜索过程中，如果发现当前状态已经不可能达到最优解，就直接返回。

以下是使用记忆化搜索和剪枝优化后的背包问题回溯法代码：

def backtrack(i, j, memo, weights, values, capacity):
    if memo[i][j] != -1:
        return memo[i][j]
    if i == 0 or j == 0:
        memo[i][j] = 0
    elif weights[i-1] > j:
        memo[i][j] = backtrack(i-1, j, memo, weights, values, capacity)
    else:
        memo[i][j] = max(backtrack(i-1, j, memo, weights, values, capacity), 
                         values[i-1] + backtrack(i-1, j-weights[i-1], memo, weights, values, capacity))
    return memo[i][j]

def knapsack(weights, values, capacity):
    n = len(weights)
    memo = [[-1] * (capacity+1) for _ in range(n+1)]
    return backtrack(n, capacity, memo, weights, values, capacity)

其中，`memo`是一个二维数组，用来保存已经计算过的状态。初始值为-1。如果`memo[i][j]`不为-1，表示已经计算过，直接返回。`weights`和`values`分别表示每个物品的重量和价值。`capacity`表示背包的容量。

在`backtrack`函数中，如果`i==0`或者`j==0`，表示已经处理完所有物品或者背包容量为0，直接返回0。如果当前物品的重量大于背包容量，不能放入背包，回溯到下一个物品。如果当前物品可以放入背包，有两种选择：放或者不放。如果不放，回溯到下一个物品。如果放，价值增加，背包容量减少，回溯到下一个物品。在两种选择中取价值最大的那一种。

在`knapsack`函数中，调用`backtrack`函数计算最优解。

这个算法的时间复杂度为O(nC)，其中n是物品数量，C是背包容量。记忆化搜索和剪枝优化可以大大减少计算量，将时间复杂度从指数级别降到了多项式级别。