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关的地图具有一个特点：没有村庄。由此可以得出两个推论：

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

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

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

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

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

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

可以接受了