当前位置: 首页> 汽车> 报价 > 集图网_中国工程造价网_网络营销推广方式包括_免费推广的app有哪些

集图网_中国工程造价网_网络营销推广方式包括_免费推广的app有哪些

时间:2025/7/11 19:48:38来源:https://blog.csdn.net/2301_80759678/article/details/146987716 浏览次数: 0次
集图网_中国工程造价网_网络营销推广方式包括_免费推广的app有哪些

蓝桥杯快到了,很多小伙伴私信小编,想让我介绍一些基础的算法,那么今天它来了!

动态规划是一种通过将复杂问题分解为重叠子问题,并记录子问题解来避免重复计算的方法。其核心是状态定义状态转移方程。在竞赛中,DP常用于解决最优化问题(如最大值、最小值)或计数问题(如路径总数)。典型的应用场景包括背包问题、最长子序列、路径规划等。


洛谷题目推荐:P1048 [NOIP2005 普及组] 采药

题目链接:P1048 采药
题目大意:有 T 秒时间采药,药田中有 M 株草药,每株草药需要 t[i] 秒采摘,价值为 w[i]。求在规定时间内能采到的草药最大总价值。


题目分析

  1. 问题转化:经典的 01背包问题。将时间视为背包容量,草药视为物品,目标是选出物品使得总重量不超过容量且总价值最大。

  2. 状态定义:定义 dp[j] 表示使用 j 秒时间能获得的最大价值。

  3. 状态转移:对每株草药 i,从后向前遍历时间 j(避免重复选取):

    dp[j] = max(dp[j], dp[j - t[i]] + w[i]);

  4. 初始化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;
}

 

代码解析

  1. 输入处理:读取总时间 T 和草药数量 M,存储每株草药的时间和价值。

  2. 动态规划过程

    • 外层循环:遍历每株草药,逐个考虑是否选择。

    • 内层循环:从 T 倒序遍历到 t[i],确保每个草药最多被选一次。

    • 状态转移dp[j] 取“不选当前草药”和“选当前草药”中的最大值。

  3. 输出结果dp[T] 即为在 T 秒内能获得的最大价值。


注意事项

  • 倒序遍历的意义:正序遍历会导致同一株草药被重复选取(完全背包问题),倒序保证每个物品只选一次。

  • 空间优化:使用一维数组代替二维数组,降低空间复杂度至 O(T)

  • 边界条件:当 j < t[i] 时无法选择当前草药,直接跳过。


扩展思考

动态规划的难点在于如何定义状态找到状态转移方程。本题中,背包容量(时间)和物品价值(草药)的模型非常典型,类似的问题可以抽象为“资源分配”问题。例如:

  • 资金预算分配(最大利润)

  • 时间安排(最多任务数)

  • 容器装载(最大利用率)

通过练习类似题目(如洛谷 P1060 [NOIP2006 普及组] 开心的金明),可以进一步掌握一维背包问题的变种。

关键字:集图网_中国工程造价网_网络营销推广方式包括_免费推广的app有哪些

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: