01背包问题递归算法

01背包问题是动态规划中的一个经典问题，它涉及到在给定的一组物品中，每个物品有自己的重量和价值，如何选择物品放入一个容量有限的背包中，使得背包中的总价值最大。递归算法是解决这个问题的一种方法，通常采用贪心策略的逆过程来构建。

递归算法的基本思路是：
1. **基本情况**：如果背包容量为0，或者所有物品都已经考虑完毕，那么背包中不能装任何物品，价值为0。
2. **递归步骤**：对于剩余的物品，有两种选择：
- **包含当前物品**：将当前物品放入背包，然后递归地计算剩余容量和剩余物品所能达到的最大价值（称为`include`）。
- **不包含当前物品**：继续考虑下一个物品（称为`exclude`），因为背包已经放不下这个物品了。
3. **合并结果**：将包含当前物品的情况和不包含当前物品的情况取较大值，作为当前状态（当前容量和当前物品）的最大价值。

递归代码示例（Python）：

def knapsack_recursion(W, wt, val, n):
    if n == 0 or W == 0: 
        return 0
    if wt[n-1] > W: 
        # 如果物品超重，就不能装
        return knapsack_recursion(W, wt, val, n-1] + knapsack_recursion(W-wt[n-1], wt, val, n-1)
        exclude = knapsack_recursion(W, wt, val, n-1)
        return max(include, exclude)

# 参数解释：
# W：背包容量
# wt：物品重量数组
# val：物品价值数组
# n：物品数量