动态规划解决汽车加油行驶最省费用路径

本实验报告由沈嘉樑（学号2014212065）于2016-2017学年第一学期在北京邮电大学软件学院完成，针对的是算法分析与设计课程中的实验项目——动态规划法的应用。实验主要包括三个部分： 1. 基本题1：0-1背包问题 这个问题旨在考察学生对动态规划的理解。给定n种物品，每种物品有自己的重量（wi）和价值（vi），以及一个固定背包容量C。目标是通过选择合适的物品组合，使放入背包的物品总价值最大化，同时不超过背包容量限制。 2. 基本题2：广告牌选取问题 学生需要管理公路广告牌的布局，考虑到收益（ri）和相邻广告牌之间的最小距离（5英里）。目标是确定最佳的广告牌位置组合，以获取最大的总收益，同时满足国家公路局的间距要求。 3. 提高题1：汽车加油行驶问题 在一个N*N的网格中，汽车从左上角出发至右下角，需要遵循一系列规则：只能沿网格边行驶，遇到油库则加油并付费A；若行驶方向改变需支付B费；在必要时增加油库需额外付费C。目标是在遵守所有规则的前提下，找到总费用最低的最优行驶路线，其中涉及到路径规划和动态规划的思想。 4. 提高题2：实际编程环境 实验环境设定为Windows 10操作系统和Visual Studio 2015集成开发环境。除了理论问题，还包括编程实现部分，如01背包问题的解决方案、广告牌选取问题的代码编写，以及子序列问题的判断。 整个实验强调了动态规划算法在实际问题中的应用，不仅要求学生理解和掌握动态规划的设计思想，还锻炼了他们将理论知识转化为实际编码能力。通过解决这些题目，学生不仅能提升算法设计技能，还能培养解决复杂问题的能力。