动态规划是一种常用的优化技术，可用于解决具有重叠子问题和最优子结构性质的问题。它通过将问题分解成更小的子问题，并存储子问题的解，从而避免了重复计算，提高了算法效率。
01背包问题是动态规划中的经典问题之一。给定一个背包容量和一组物品，每个物品都有对应的重量和价值。目标是选择一些物品放入背包，使得在背包容量限制下所能装载的物品总价值最大化，且每个物品只能选择一次。
完全背包问题与01背包类似，但不同之处在于每个物品可以选择多次放入背包。也就是说，每个物品的数量是无限的，目标仍然是最大化装载的物品总价值。
下面是一个简单的示例代码，展示了如何使用动态规划解决01背包问题和完全背包问题：
# 01背包问题
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])
else:
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
# 完全背包问题
def knapsack_complete(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]])
return dp[capacity]
# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print("01背包问题最大价值:", knapsack_01(weights, values, capacity))
print("完全背包问题最大价值:", knapsack_complete(weights, values, capacity))这段代码展示了如何使用动态规划解决01背包问题和完全背包问题。通过构建一个二维数组或一维数组来存储子问题的解，并使用迭代的方式计算最终结果。
区别在于状态转移方程的不同：
- 01背包问题的状态转移方程：
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]) - 完全背包问题的状态转移方程：
dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]])
通过对比可以看出，01背包问题的状态转移方程中需要比较上一行的结果，而完全背包问题则只需要比较当前行的结果。这是因为完全背包问题允许重复选择物品，因此每一次迭代都要考虑当前物品是否放入背包。