01背包问题python（使用递归和动态规划）

好的，下面我将分别给出递归和动态规划的解法，并使用 Python 代码来实现。

01背包问题是一个经典的动态规划问题，其表述如下：有一个背包，容量为C，有n个物品，每个物品有重量w和价值v，现在要把这些物品放入背包中，使得背包中物品的总价值最大，求最大价值。

1. 递归解法

递归解法比较简单，但是由于存在大量的重复计算，效率比较低。具体思路是：对于每个物品，有两种选择，放入背包或不放入背包，然后递归处理剩下的物品。

代码如下：

def knapsack01_recursion(C, w, v, n):
    if n == 0 or C == 0:
        return 0
    if w[n-1] > C:
        return knapsack01_recursion(C, w, v, n-1)
    else:
        return max(v[n-1] + knapsack01_recursion(C-w[n-1], w, v, n-1), knapsack01_recursion(C, w, v, n-1))

2. 动态规划解法

动态规划解法使用一个二维数组来存储中间状态，具体思路是：定义一个二维数组dp[i][j]，表示前i个物品放入容量为j的背包中可以获得的最大价值。对于每个物品，有两种选择，放入背包或不放入背包，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])，其中w[i-1]和v[i-1]分别表示第i个物品的重量和价值。

最终的结果为dp[n][C]。

代码如下：

def knapsack01_dp(C, w, v, n):
    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 w[i-1] > j:
                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]

以上就是使用递归和动态规划解决01背包问题的Python代码实现。