01背包问题解题方法：动态规划、回溯法、分支限界法

### 01背包问题的三种主要解法 #### 动态规划求解0-1背包问题 对于0-1背包问题，动态规划提供了一种高效的方法来寻找最优解。该方法通过构建一个二维数组`dp[i][j]`表示前i个物品放入容量为j的背包可以获得的最大价值。状态转移方程如下： \[ dp[i][w]=\max(dp[i−1][w],dp[i−1][w-w_i]+v_i) \] 其中\( w_i \) 和 \( v_i \) 分别代表第 i 件商品的重量和价值[^1]。 ```python def knapsack_dp(weights, values, capacity): n = len(values) # 创建二维列表存储子问题的结果 dp = [[0 for _ in range(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], dp[i - 1][j - weights[i - 1]] + values[i - 1]) else: dp[i][j] = dp[i - 1][j] return dp[n][capacity] ``` #### 回溯法求解0-1背包问题 回溯法则是一种基于深度优先搜索策略解决问题的方式。这种方法会尝试每一种可能的选择组合直到找到满足条件的最佳方案为止。当遇到不满足约束的情况时立即返回并调整当前决策路径继续探索其他可能性[^3]。 ```python best_value = 0 current_weight = 0 current_value = 0 solution_vector = [] def backtrack_knapsack(index, weights, values, capacity): global best_value, current_weight, current_value, solution_vector if index >= len(weights): if current_value > best_value and current_weight <= capacity: best_value = current_value return # 不选当前物品 backtrack_knapsack(index + 1, weights, values, capacity) # 如果选择此物不会超过总重则考虑加入 if (current_weight + weights[index]) <= capacity: current_weight += weights[index] current_value += values[index] # 更新临时解向量 temp_solution = list(solution_vector) temp_solution.append(index) # 尝试选取下一个物品之前保存现场 backtrack_knapsack(index + 1, weights, values, capacity) # 还原现场以便后续操作 current_weight -= weights[index] current_value -= values[index] ``` #### 分支限界法求解0-1背包问题 分支限界法采用广度优先或最小耗费（最大效益）优先的原则遍历解空间树，在每次迭代过程中都维护着一组候选节点集合，并从中挑选最有潜力的一个进行深入考察直至获得全局最优解。为了提高效率通常还会设置界限函数提前剪枝那些不可能产生更优结果的部分子树从而减少不必要的计算开销[^4]。 ```python from queue import PriorityQueue class Node(object): def __init__(self, level, profit, weight, bound, include): self.level = level self.profit = profit self.weight = weight self.bound = bound self.include = include def __lt__(self, other): return self.bound < other.bound def promising(node, p, w, W, n): totalWeight = node.weight bound = node.profit j = node.level + 1 while j < n and totalWeight + w[j] <= W: totalWeight += w[j] bound += p[j] j += 1 k = j if k < n: bound += (W-totalWeight)*p[k]/w[k] return bound def branch_and_bound(p, w, W, n): Q = PriorityQueue() u = Node(-1, 0, 0, 0, []) maxProfit = 0 v = None Q.put((-promising(u,p,w,W,n),u)) while not Q.empty(): _, u = Q.get() if u.level == -1: v = Node(0, 0, 0, 0, []) if u.level == n-1: continue v.level = u.level + 1 # Include next item v.weight = u.weight + w[v.level] v.profit = u.profit + p[v.level] v.include = list(u.include) v.include.append(v.level) if v.weight <= W and v.profit > maxProfit: maxProfit = v.profit v.bound = promising(v, p, w, W, n) if v.bound > maxProfit: Q.put((-v.bound,v)) # Exclude next item v.weight = u.weight v.profit = u.profit v.include.pop() if len(v.include)>0 else None v.bound = promising(v, p, w, W, n) if v.bound > maxProfit: Q.put((-v.bound,v)) return maxProfit ```