蓝桥杯快到了,很多小伙伴私信小编,想让我介绍一些基础的算法,那么今天它来了!
动态规划是一种通过将复杂问题分解为重叠子问题,并记录子问题解来避免重复计算的方法。其核心是状态定义和状态转移方程。在竞赛中,DP常用于解决最优化问题(如最大值、最小值)或计数问题(如路径总数)。典型的应用场景包括背包问题、最长子序列、路径规划等。
洛谷题目推荐:P1048 [NOIP2005 普及组] 采药
题目链接:P1048 采药
题目大意:有 T
秒时间采药,药田中有 M
株草药,每株草药需要 t[i]
秒采摘,价值为 w[i]
。求在规定时间内能采到的草药最大总价值。
题目分析
-
问题转化:经典的 01背包问题。将时间视为背包容量,草药视为物品,目标是选出物品使得总重量不超过容量且总价值最大。
-
状态定义:定义
dp[j]
表示使用j
秒时间能获得的最大价值。 -
状态转移:对每株草药
i
,从后向前遍历时间j
(避免重复选取):dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
-
初始化:
dp
数组初始化为 0,表示未选择任何草药时的价值为 0。
关键代码解读(C++)
#include <bits/stdc++.h>
using namespace std;const int MAXT = 1005;
int dp[MAXT]; // dp[j]: 使用j秒的最大价值
int t[105], w[105]; // 每株草药的时间和价值int main() {int T, M;cin >> T >> M;for (int i = 1; i <= M; i++) {cin >> t[i] >> w[i];}// 动态规划核心for (int i = 1; i <= M; i++) { // 遍历所有草药for (int j = T; j >= t[i]; j--) { // 倒序更新,防止重复选取dp[j] = max(dp[j], dp[j - t[i]] + w[i]);}}cout << dp[T] << endl; // 输出最大价值return 0;
}
代码解析:
-
输入处理:读取总时间
T
和草药数量M
,存储每株草药的时间和价值。 -
动态规划过程:
-
外层循环:遍历每株草药,逐个考虑是否选择。
-
内层循环:从
T
倒序遍历到t[i]
,确保每个草药最多被选一次。 -
状态转移:
dp[j]
取“不选当前草药”和“选当前草药”中的最大值。
-
-
输出结果:
dp[T]
即为在T
秒内能获得的最大价值。
注意事项
-
倒序遍历的意义:正序遍历会导致同一株草药被重复选取(完全背包问题),倒序保证每个物品只选一次。
-
空间优化:使用一维数组代替二维数组,降低空间复杂度至
O(T)
。 -
边界条件:当
j < t[i]
时无法选择当前草药,直接跳过。
扩展思考
动态规划的难点在于如何定义状态和找到状态转移方程。本题中,背包容量(时间)和物品价值(草药)的模型非常典型,类似的问题可以抽象为“资源分配”问题。例如:
-
资金预算分配(最大利润)
-
时间安排(最多任务数)
-
容器装载(最大利用率)
通过练习类似题目(如洛谷 P1060 [NOIP2006 普及组] 开心的金明),可以进一步掌握一维背包问题的变种。