欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 时评 > 【蓝桥杯】算法笔记2

【蓝桥杯】算法笔记2

2025/4/7 20:12:14 来源:https://blog.csdn.net/Winkyyyyyy/article/details/146902476  浏览:    关键词:【蓝桥杯】算法笔记2

这篇文章主要记录动态规划方面的学习。

动态规划的核心思想:

把大问题分解成小问题,记住小问题的解,避免重复计算。

动态规划(DP)的三大特点

①最优子结构:大问题的最优解可以由小问题的最优解推导出来

②重叠子问题:在求解过程中会反复遇到相同的小问题

③无后效性:当前状态一旦确定,后续过程不受之前决策的影响


🎒0-1背包问题

🛒 生活化题目:吃货的购物计划

题目:妈妈给你一个限重5kg的购物袋,超市有以下零食:

零食重量好吃度
薯片2kg4
可乐3kg5
糖果1kg3
饼干2kg3

规则

  1. 购物袋不能超重(≤5kg)

  2. 每种零食只能拿一件

  3. 目标是让总"好吃度"最高

🧩 分步思考图解

第0步:初始化表格(空包状态)

容量0kg1kg2kg3kg4kg5kg
价值000000

第1步:考虑薯片(2kg,好吃度4)

if 当前容量 >= 2kg:价值 = max(不装的价值, 装的价值 = 剩余容量的价值 + 4)
容量0kg1kg2kg3kg4kg5kg
价值004444

第2步:加入可乐(3kg,好吃度5)

# 容量3kg时:
max(不装=4, 装=0kg价值0 + 5 =5) → 选5
# 容量5kg时:
max(不装=4, 装=2kg价值4 +5=9) → 选9
容量0kg1kg2kg3kg4kg5kg
价值004559

第3步:加入糖果(1kg,好吃度3)

# 容量1kg时:
max(不装=0, 装=0kg价值0 +3=3) → 选3
# 容量4kg时:
max(不装=5, 装=3kg价值5 +3=8) → 选8
容量0kg1kg2kg3kg4kg

版权声明:

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

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

热搜词