GitHub

您所在的位置：网站首页 › 2000年数学建模b题matlab代码 › GitHub

GitHub

2024-04-14 00:57| 来源: 网络整理| 查看: 265

2020MCM-B穿越沙漠

2020全国大学生数学建模B题-穿越沙漠-动态规划

最终结果（B问）与标答完全相同 RUNNABLE UNDER gcc7.3 第一问

程序： B1.cpp

数据：data1.txt, data2.txt

思路：从后向前递推

建立目标函数F（x,y,z1，z2）代表到达目标状态时能留下的最大钱数（统计时间为当天结束时）

X表示当前天数，y表示当前位置，z1表示当前食物数量，z2表示当前水数量

则F满足以下递推式：

F（x,y,z1，z2）=max{ F(x,y-1,z1+deltaz1,z2+deltaz2) ， %上一天原地休整 F(xi,y-1,z1+2*deltaz1,z2+2*deltaz2) %上一天自相邻的xi处行至 F(x,y-1,z1+3*deltaz1,z2+3*deltaz2)+1000 % x处为矿山且上一天挖矿 F(x,y,z1-z3,z2-z4)-cost(z3,z4) %x处为村庄且购买z3,z4的物资 }

即F为以上四项中的最大值

推导到终点即可

第二问

程序：B2.cpp

数据：data3.txt, data4.txt

思路：

F（x,y,z1，z2）=max{ F(x,y+1,z1-deltaz1,z2-deltaz2) ， %今天原地休整 F(xi,y+1,z1-2*deltaz1,z2-2*deltaz2) %今天自相邻的xi处行至 F(x,y+1,z1-3*deltaz1,z2-3*deltaz2)+1000 % x处为矿山且今天挖矿 F(x,y,z1+z3,z2+z4)-cost(z3,z4) %x处为村庄且购买z3,z4的物资 }

根据当天天气不同，F可能会有3种不同的取值，所以期望就是，三者分别乘以对应的天气出现的概率。游戏失败的惩罚-maxnum。

第五问

注意到第5关的地图具有一个特点：没有村庄。由此可以得出两个推论：

随着天数的增加，两人食物与水的量只会减少不会增加，即两人的负重随时间是单调的。

食物与水的购买价只有一种选择。

所以我们可以做这样一个操作：在起点购买水和食物时对开销不加统计，而是在水和食物被消耗统计消耗的食物与水的价值，这样一来我们就不需要知道背包中具体有多少水和食物，我们只要在水和食物被消耗时，能够从背包中拿出相应数量的水和食物以便统计开销即可，换句话说我们只需知道当前的负重即可，至于负重中有多少是水多少是食物，我们不关心。于是函数可以简化为

F（day,place1,place2,weight1,weight2）

计算量（时间与空间复杂度）约为

1200kg $\times$ 1200kg $\times$ 10天 $\times$ 10个点 $\times$ 10个点=14亿

可以接受了

【本文地址】

GitHub

GitHub

今日新闻

推荐新闻