一、递归，回溯，迭代
在开始回溯算法前，我想先弄清这三个的关系
递归是指一个函数在定义中直接或间接地调用自身，递归表现为调用函数本身，通过将问题分解为子问题来逐步解决。
回溯算法会在搜索过程中尝试一个方案，如果发现当前方案无法满足要求，就“回退”到上一个步骤，尝试其他方案。
迭代是利用循环语句实现，而循环，单纯是实现反复执行某个功能，以减少重复书写通常是while，for循环。
二、背包问题
完全背包问题和 0-1 背包问题的主要区别在于，在完全背包问题中，每个物品可以选择放入背包多次（而不是一次）。
完全背包：
在完全背包问题中，每个物品可以被选择多次。
完全背包问题 中，dp[w] 表示的是背包容量为 w 时能得到的最大价值，并且每个物品可以被选择多次。对于每个物品 i，我们都会尝试多次将该物品放入背包，不会受到只能选择一次的限制。所以我们不需要区分物品的层级。
def knapsack_complete(weights, values, capacity):
n = len(weights)
# 初始化DP表
dp = [0] * (capacity + 1)
# 填充DP表
for i in range(n): # 遍历每个物品
for w in range(weights[i], capacity + 1): # 当前容量从 weights[i] 开始
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
# dp[capacity] 是最大价值
return dp[capacity]
weights = [1, 2, 3] # 物品的重量
values = [6, 10, 12] # 物品的价值
capacity = 5 # 背包容量
print(knapsack_complete(weights, values, capacity)) # 输出: 30
01背包：
在0-1背包问题中，每个物品只能选一次，要么选，要么不选。
dp[i - 1][w]表示的是考虑前 i 个物品(最后一个物品放不进去，不放)，背包容量为w时能得到的最大价值。
dp[i - 1][w - weights[i - 1]] + values[i - 1]表示的是(最后一个物品能放进去)得到的最大价值
def knapsack_01(weights, values, W):
n = len(weights)
# 创建一个二维DP数组，dp[i][w]表示前i个物品，背包容量为w时的最大价值
dp = [[0] * (W + 1) for _ in range(n + 1)]
# 填充DP表格
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w:
# 如果当前物品可以放入背包，选择放或不放
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
# 当前物品无法放入背包，选择不放
dp[i][w] = dp[i - 1][w]
# 返回最大价值
return dp[n][W]
# 示例
weights = [2, 3, 4, 5] # 物品重量
values = [3, 4, 5, 6] # 物品价值
W = 5 # 背包最大容量
result = knapsack_01(weights, values, W)
print(f"最大价值: {result}")
- 0-1背包问题 的状态转移依赖于 上一层 的选择，因此需要用二维数组来记录每个物品和每个容量的状态。
- 完全背包问题 中，每个物品可以选择多次，所以我们可以通过一个一维数组来记录当前背包容量下的最大价值。