0-1背包问题动态规划法

0-1背包问题是一个经典的动态规划问题，它的解法是使用动态规划算法。

假设有一个背包，它的容量为C，现在有n个物品，每个物品有两个属性，重量w和价值v。问题是如何选择物品，使得装进背包中的物品总重量不超过C，且总价值最大。

定义一个二维数组dp[i][j]，表示前i个物品中，选取总重量不超过j的物品的最大价值。则状态转移方程为：

- 当j < w[i]时，dp[i][j] = dp[i-1][j]，表示第i个物品不能选，只能选择前i-1个物品。
- 当j >= w[i]时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，表示第i个物品可以选，那么就需要在前i-1个物品中选取总重量不超过j-w[i]的物品，使得价值最大，再加上第i个物品的价值v[i]，就是总重量不超过j时的最大价值。

最终的答案就是dp[n][C]。

下面是Python代码实现：

def knapsack(w, v, C):
    n = len(w)
    dp = [[0]*(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]

其中，w和v分别是物品的重量和价值，C是背包的容量，n是物品的数量。