C++ 动态规划入门：从“配备书的方案”题解到背包问题 3 种变体

C 动态规划入门从组合问题到背包问题变体实战1. 动态规划基础与解题框架动态规划Dynamic Programming简称DP作为算法设计中的核心思想通过将复杂问题分解为相互重叠的子问题并存储子问题的解以避免重复计算显著提升了算法效率。理解动态规划需要掌握三个关键特征最优子结构问题的最优解包含其子问题的最优解重叠子问题不同的决策序列会到达相同的子问题状态转移方程定义如何从一个状态推导出另一个状态让我们通过一个典型问题建立DP思维模型。考虑配备书的方案问题给定m类书籍每类有不同数量要选出n本书放在书架上求有多少种选择方案需对202307取模。通用DP解题模板// 初始化DP数组通常dp[0] 1表示基本情况 vectorint dp(total 1, 0); dp[0] 1; // 遍历所有物品类别 for (int i 0; i categories; i) { // 逆向遍历目标值防止重复计数 for (int j total; j 0; --j) { // 遍历当前物品可能的选取数量 for (int k 1; k min(available[i], j); k) { // 状态转移 dp[j] (dp[j] dp[j - k]) % MOD; } } } return dp[total];这个模板体现了DP的核心思想记忆化存储中间结果和递推关系。在实际应用中我们需要根据问题特点调整状态定义和转移方程。2. 经典背包问题解析背包问题是动态规划的标杆题型主要包含三种基本变体2.1 0-1背包问题问题描述给定n件物品和一个容量为V的背包物品i的重量是w[i]价值是v[i]每种物品只有一件求不超过背包容量的最大价值。状态定义dp[i][j]考虑前i件物品背包容量为j时的最大价值状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) // 不选或选第i件物品空间优化后的C实现int knapsack01(vectorint weights, vectorint values, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { for (int j capacity; j weights[i]; --j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }关键点内层循环必须逆向遍历确保每个物品只被选取一次2.2 完全背包问题问题描述与0-1背包类似但每种物品有无限件可用。状态转移变化dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]) // 注意第二个是dp[i]而非dp[i-1]优化实现int unboundedKnapsack(vectorint weights, vectorint values, int capacity) { vectorint dp(capacity 1, 0); for (int i 0; i weights.size(); i) { for (int j weights[i]; j capacity; j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }差异点内层循环正向遍历允许物品重复选取2.3 多重背包问题问题描述每种物品有确定的件数限制既不是唯一也不是无限。解决方案二进制拆分法将物品拆分为1,2,4,...2^k的组合转化为0-1背包单调队列优化维护滑动窗口最大值时间复杂度O(VN)二进制拆分实现int multipleKnapsack(vectorint weights, vectorint values, vectorint counts, int capacity) { vectorpairint, int items; // (weight, value) // 二进制拆分 for (int i 0; i weights.size(); i) { for (int k 1; k counts[i]; k * 2) { items.emplace_back(k * weights[i], k * values[i]); counts[i] - k; } if (counts[i] 0) { items.emplace_back(counts[i] * weights[i], counts[i] * values[i]); } } // 0-1背包解法 vectorint dp(capacity 1, 0); for (auto [w, v] : items) { for (int j capacity; j w; --j) { dp[j] max(dp[j], dp[j - w] v); } } return dp[capacity]; }3. 动态规划优化技巧3.1 空间压缩技术观察状态转移方程当前状态往往只与前一状态相关因此可将二维DP压缩为一维优化前优化后dp[i][j]dp[j]需要保存全部状态只需保存当前状态3.2 常见优化策略对比优化方法适用场景时间复杂度空间复杂度滚动数组状态转移只依赖有限前驱不变O(N)→O(1)单调队列特定形式的状态转移方程O(N²)→O(N)不变斜率优化决策单调性问题O(N²)→O(N)不变3.3 边界条件处理技巧// 初始化技巧根据问题要求设置初始值 vectorint dp(capacity 1, -INF); // 求最大值时初始为负无穷 dp[0] 0; // 基础状态 // 遍历时的越界检查 for (int j capacity; j w; --j) { if (dp[j - w] ! -INF) { // 确保前驱状态有效 dp[j] max(dp[j], dp[j - w] v); } }4. 实战案例滑雪板打包问题让我们分析输入中的滑雪板打包问题需要将不同长度和重量的滑雪板打包每次打包需使用两根相同长度的木板固定且总重量不超过G求最少需要多长的木板。问题转化将滑雪板按长度降序排序每次尝试将最长的可用滑雪板打包计算所需木板总长度DP解法思路int minTotalLength(vectorpairint, int skis, int G) { sort(skis.rbegin(), skis.rend()); // 按长度降序 int total 0; while (!skis.empty()) { int current_len skis[0].first; int current_weight 0; // 贪心选择可打包的滑雪板 auto it skis.begin(); while (it ! skis.end() current_weight it-second G) { if (it-first current_len) { current_weight it-second; it skis.erase(it); } else { it; } } total 2 * current_len; // 两根木板 } return total; }这个案例展示了如何将实际问题转化为组合优化问题并采用贪心与DP结合的解法。在实际编码竞赛中理解问题本质比套用算法模板更重要。