python备忘录算法解决01背包问题

01背包问题是经典的动态规划问题，其主要思想是利用递推的方式，将问题分解为子问题来求解。

假设有n个物品，每个物品有一个重量w[i]和一个价值v[i]，现在有一个容量为C的背包，问如何选择物品能够使得背包中的总价值最大。

下面是Python代码实现：

def knapsack(C, w, v):
    n = len(w)
    # 初始化状态矩阵
    dp = [[0 for _ in range(C+1)] for _ in range(n+1)]
    # 递推计算状态矩阵
    for i in range(1, n+1):
        for j in range(1, C+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
    # 返回最优解
    return dp[n][C]

其中，状态矩阵dp[i][j]表示在前i个物品中，容量为j的背包中所能得到的最大价值。

时间复杂度为O(nC)，空间复杂度为O(nC)。