动态规划算法dp01背包与完全背包

### 动态规划中的01背包与完全背包问题 #### 01背包问题概述 在01背包问题中，每种物品仅有一件，可以选择放入或者不放入背包。定义状态 `dp[j]` 表示当背包容量为 `j` 时能够获得的最大价值[^2]。 对于每一个物品 `i` 和其对应的重量 `w[i]` 及价值 `v[i]`，可以通过如下状态转移方程计算最大价值： ```python for i in range(1, n+1): # 遍历每个物品 for j in range(W, w[i]-1, -1): # 倒序遍历背包容量 dp[j] = max(dp[j], dp[j-w[i]] + v[i]) # 不选或选择当前物品 ``` 上述代码的核心在于倒序更新背包容量以避免重复利用同一件物品[^4]。 --- #### 完全背包问题概述 在完全背包问题中，每种物品的数量无限多，可以多次选取同一物品来填充背包。同样定义状态 `dp[j]` 表示当背包容量为 `j` 时能获取的最大价值[^3]。 此时的状态转移方程略有不同，因为允许重复选择同一个物品，因此需要正向遍历背包容量： ```python for i in range(1, n+1): # 遍历每个物品 for j in range(w[i], W+1): # 正序遍历背包容量 dp[j] = max(dp[j], dp[j-w[i]] + v[i]) # 不选或选择当前物品 ``` 通过正向遍历，每次更新都基于已经考虑过相同物品的情况，从而实现了对单个物品的多次选择。 --- #### 主要区别对比 | 特性 | 01背包问题 | 完全背包问题 | |-----------------|-------------------------------------|-----------------------------------| | **物品数量** | 每种物品最多只能取一次 | 同一种物品可被取任意次 | | **遍历顺序** | 背包容量需倒序遍历 | 背包容量需正序遍历 | | **时间复杂度** | O(n * W) | O(n * W) | 尽管两者的时间复杂度表面上一致，但由于实现细节的不同，在实际运行效率上可能存在差异。 --- #### 示例代码比较 ##### 01背包问题实现 以下是解决01背包问题的一个简单Python实现： ```python def zero_one_knapsack(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(capacity, weights[i]-1, -1): dp[j] = max(dp[j], dp[j-weights[i]] + values[i]) return dp[capacity] # 测试数据 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 8 print(zero_one_knapsack(weights, values, capacity)) ``` ##### 完全背包问题实现 下面是针对完全背包问题的一种Python实现方法： ```python def complete_knapsack(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(weights[i], capacity+1): dp[j] = max(dp[j], dp[j-weights[i]] + values[i]) return dp[capacity] # 测试数据 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 8 print(complete_knapsack(weights, values, capacity)) ``` ---