回溯法与动态规划在组合优化问题中的应用-育师

1. 问题背景与需求分析

小明减肥这个问题源自华为OD机考双机位A卷，是一个典型的组合优化问题。题目描述大致是：小明需要制定一个减肥计划，在给定的时间段内通过合理安排运动和饮食来达到最佳减肥效果。这实际上可以抽象为一个组合选择问题——从若干运动项目和饮食方案中选择最优组合，使得总消耗卡路里最大（或体重减少最多），同时满足时间、营养等约束条件。

这类问题在实际生活中非常常见：

健身计划制定：选择训练动作和组数
投资组合优化：选择股票和配置比例
课程安排：选择课程和时间段

2. 算法选型思路

2.1 回溯法适用场景

回溯法特别适合解决这类需要尝试所有可能组合的问题：

解空间呈现树状结构
需要找出所有满足条件的解
问题通常有"选择/不选择"这样的决策点

在本题中，每个运动/饮食方案就是一个决策点——要么选，要么不选。

2.2 动态规划适用场景

动态规划则适用于：

问题可以分解为子问题
子问题之间存在重叠
需要最优解而非所有解

如果题目要求的是"最大减肥效果"而非"所有可能的减肥方案"，DP就是更好的选择。

3. 回溯法实现详解

3.1 算法框架

def backtrack(choices, path, result, constraints): if meet_constraints(path, constraints): result.append(path.copy()) return for i in range(len(choices)): if not is_valid(choices[i], path, constraints): continue path.append(choices[i]) backtrack(choices[i+1:], path, result, constraints) path.pop()

3.2 具体实现

假设每个运动有：

消耗卡路里(cal)
所需时间(time)
类型(type)

约束条件：

总时间 ≤ max_time
运动类型不能重复

def diet_backtrack(exercises, max_time): result = [] def backtrack(start, path, current_time): if current_time > max_time: return if path: result.append(path.copy()) for i in range(start, len(exercises)): ex = exercises[i] # 检查类型是否重复 if any(e['type'] == ex['type'] for e in path): continue path.append(ex) backtrack(i+1, path, current_time + ex['time']) path.pop() backtrack(0, [], 0) return result

3.3 优化技巧

提前排序：按cal/time降序排列，可以更快找到高质量解
剪枝策略：
- 当前时间 + 剩余所有运动最小时间 > max_time时直接返回
- 记录当前最大收益，剩余运动最大可能收益不够时剪枝

4. 动态规划实现详解

4.1 状态定义

这是一个二维背包问题：

一维是时间限制
一维是运动类型去重

为简化，我们先考虑时间维度： dp[i][t] = 前i个运动中，时间不超过t的最大卡路里消耗

4.2 状态转移方程

对于每个运动，有两种选择：

不选：dp[i][t] = dp[i-1][t]
选：dp[i][t] = dp[i-1][t-time] + cal

取较大值： dp[i][t] = max(dp[i-1][t], dp[i-1][t-time] + cal)

4.3 具体实现

def diet_dp(exercises, max_time): n = len(exercises) dp = [[0]*(max_time+1) for _ in range(n+1)] for i in range(1, n+1): ex = exercises[i-1] for t in range(max_time+1): if ex['time'] > t: dp[i][t] = dp[i-1][t] else: dp[i][t] = max( dp[i-1][t], dp[i-1][t-ex['time']] + ex['cal'] ) # 回溯找出具体方案 res = [] t = max_time for i in range(n, 0, -1): if dp[i][t] != dp[i-1][t]: res.append(exercises[i-1]) t -= exercises[i-1]['time'] return dp[n][max_time], res[::-1]

4.4 空间优化

可以压缩为一维数组：

def diet_dp_optimized(exercises, max_time): dp = [0]*(max_time+1) for ex in exercises: for t in range(max_time, ex['time']-1, -1): dp[t] = max(dp[t], dp[t-ex['time']] + ex['cal']) return dp[max_time]

5. 两种算法对比

维度	回溯法	动态规划
时间复杂度	O(2^n)	O(n*max_time)
空间复杂度	O(n)递归栈	O(n*max_time)或O(max_time)
适用场景	需要所有解	需要最优解
优势	实现简单，能找到所有解	效率高，适合大数据量
劣势	数据量大时性能差	只能得到一个最优解

6. 实际应用中的注意事项

数据预处理很重要：
- 去除明显不合理的运动（如时间>max_time的）
- 对相似运动进行分组

约束条件的处理：

# 示例：增加营养约束 def is_valid(path, new_exercise): total_protein = sum(e['protein'] for e in path) + new_exercise['protein'] return total_protein <= max_protein