200字范文 > 数学建模B题穿越沙漠

数学建模B题穿越沙漠

时间：2024-07-03 09:30:45

相关推荐

数学建模B题穿越沙漠

1.题目

考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。

游戏的基本规则如下：

（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。

（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。

（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。

（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。

（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的倍。

（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。

（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。

（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。

请根据游戏的不同设定，建立数学模型，解决以下问题。

假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入Result.xlsx。假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。

2.解题思路与第一关与第二关

有三大种思路

1.动态规划

2.简略地图后使用Dijkstra算法来解决

3.分析题干然后建立模型利用groubi,lingo求解最优解

2.1 动态规划情况

设状态dp[k][j][w][f]代表第k天时在第j个点剩余水为w箱剩余食物为f箱的最大资金，则：

ans=MAXw,f,i dp[k][zd][w][f]

2.1.1 初始值设定

由于起始点可以在起点购买物资，则有初始状态

dp[0][qd][w][f]=10000−cost_water∗w−cost_food∗fw∈[0,400]f∈[0,600]

其中cost_water，cost_food 为购买水和食物消耗的钱。

这里假设起始为第0天，则第一天天气影响的是从第0天到第1天。

2.1.2 状态转移方程

当第k天人在村庄j时：

第k天为沙暴天气

dp[k+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]}=max(dp[k][j][w][f]-2*ww*cost_water-2*ff*cost_food

非沙暴天气：

dp[k+1][jj][w+ww-xh_water[tq]][f+ff-xh_food[tq]]}=max(dp[k][j][w][f]-2*ww*cost_water-2*ff*cost_food

当第k天人在矿山j时：

挖矿

dp[k+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=max(dp[k][j][w][f]+1000)

第k天为沙暴天气：

dp[k+1][j][w-xh_water[tq]][f-xh_food[tq]]=max(dp[k][j][w][f])

第k天为非沙暴天气：

dp[k+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][jj][w][f])

当第k天人在其他地区时

第k天为沙暴天气：

dp[k+1][j][w-xh_water[tq]][f-xh_food[tq]]=max(dp[k][j][w][f])

第k天为非沙暴天气：

dp[k][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][j][w][f])

2.1.3思考隐含条件约束模型

除了回村庄补充物资，不会走回头路。

除了挖矿和沙尘暴不会在原地停留。

只会走关键点之间的最短路径

2.1.4代码

第一关

#include<bits/stdc++.h>#include<iostream>using namespace std;// 点数const int N=11,M=28,inf=0x3f3f3f,Day=30;int dp[32][N+1][405][605],zd,qd,FZ;int cost_water,cost_food,walk,dig,buy;int xh_water[3]={5,8,10},xh_food[3]={7,6,10};bool cz[N+1],ks[N+1];struct node{short day; // i short from; // jj jint water,food;int money;bool operator!=(const node &x){return x.day!=day || x.from!=from || x.water!=water || x.food!=food ;};}path[31][N+1][405][605],lastpath;vector <int> weather;vector <int> g[N];map <int,int> mp;void push_back(int x,int y){g[x].push_back(y);g[y].push_back(x);}void build_map(){push_back(1,2);push_back(2,3);push_back(2,5);push_back(5,6);push_back(3,4);push_back(4,7);push_back(6,7);push_back(7,8);push_back(8,9);push_back(9,10);push_back(10,11);mp[1]=1;mp[2]=25;mp[3]=26;mp[4]=27;mp[5]=24;mp[6]=23;mp[7]=21;mp[8]=9;mp[9]=15;mp[10]=14;mp[11]=12;for(int i=1;i<=N;i++){cz[i]=0;ks[i]=0;}cz[9]=1;ks[11]=1;zd=4;qd=1;return ;}void init(){memset(dp,-inf,sizeof(dp));FZ=1200;cost_water=5;cost_food=10;walk=2;buy=2;dig=3;for(int k=0;k<=405;k++){for(int l=0;l<=601;l++){if(k*3+l*2<=FZ){dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;}}}printf("init %d\n",dp[0][1][178][333]);path[0][1][0][0]={0,0,0,0};return ;}int main(){weather={1,1,0,2,0,1,2,0,1,1,2,1,0,1,1,1,2,2,1,1,0,0,1,0,2,1,0,0,1,1,};build_map();init();for(int i=0;i<Day;i++){printf("第%d天\n",i);int tq=weather[i];for(int j=1;j<=N;j++){if(cz[j])// 村庄{for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){//购买或不够买物资(ww=0,ff=0就是不购买) if(tq==2) //停留{int money=dp[i][j][w][f];for(int ww=0;ww<=money/cost_water;ww++){for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0){if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food){dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};}}}}}else //从j走到jj{for(auto jj:g[j]){int money=dp[i][j][w][f];for(int ww=0;ww<=money/cost_water;ww++){for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0){if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food){dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};}}}}}}}}}else if (ks[j])// 矿山{for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){// 已经停留一天了，可以挖矿if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0){if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0){dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]+1000};}}// 在矿山不挖矿或不允许挖矿if(tq==2) //停留但不挖矿{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}else{if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0){for(auto jj:g[j]){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}}}}}else //普通区{for(int w=0;w<=405;w++){for(int f=0;w*3+f*2<=1200;f++){if(tq==2) //在j点停留{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}else// 走到jj点{for(auto jj:g[j]){if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};}}}}}}}}}int ans=-inf;node lastpath;int last_water=0,last_food=0,last_day=Day;for(int i=0;i<=Day;i++){for(int w=0;w<=405;w++)for(int f=0;w*3+2*f<=1200;f++){if(dp[i][zd][w][f]>ans){ans=dp[i][zd][w][f];lastpath=path[i][zd][w][f];last_water=w;last_food=f;last_day=i;}}}stack<node> s;stack<int> my;printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",last_day,weather[Day],zd,last_water,last_food,ans);s.push((node){last_day,zd,last_water,last_food,ans});while(lastpath!=path[0][1][0][0]){s.push(lastpath);printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",lastpath.day,weather[lastpath.day],mp[lastpath.from],lastpath.water,lastpath.food,lastpath.money);my.push(lastpath.money);lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];}freopen("output.txt","w",stdout);my.push(my.top());while (!s.empty()){node t=s.top();int money=my.top();printf("Day:%d weather:%d point:%d water:%d food:%d money:%d\n",t.day,weather[t.day],mp[t.from],t.water,t.food,money);s.pop();my.pop();}printf("%d\n",ans);return 0;}

第二关

#include<bits/stdc++.h>#include<iostream>using namespace std;const short N=27,inf=20000,Day=30;short dp[31][N+1][401][601],zd,qd,FZ;short cost_water,cost_food,walk,dig,buy;short xh_water[3]={5,8,10},xh_food[3]={7,6,10};bool cz[N+1],ks[N+1];struct node{char day; // i char from; // jj jshort water,food;bool operator!=(const node &x){return (x.day-'0')!=(day-'0') || (x.from-'0'!=from-'0') || (x.water-'0')!=(water-'0') || (x.food-'0'!=food-'0') ;};}path[31][N+1][401][601],lastpath;vector <short> weather;vector <short> g[N+1];map <short,short> mp;void push_back(short x,short y){g[x].push_back(y);g[y].push_back(x);}void build_map(short flag){if(flag==2){push_back(1,2);push_back(2,3);push_back(3,4);push_back(4,5);push_back(5,6);push_back(6,7);push_back(7,8);push_back(8,9);push_back(9,10);push_back(10,11);push_back(11,12);push_back(7,13);push_back(13,14);push_back(14,15);push_back(15,16);push_back(15,10);push_back(15,11);push_back(16,12);push_back(3,17);push_back(17,18);push_back(18,19);push_back(19,20);push_back(20,21);push_back(21,22);push_back(22,23);push_back(15,23);push_back(23,16);mp[1]=1;mp[2]=2;mp[3]=3;mp[4]=4;mp[5]=12;mp[6]=21;mp[7]=29;mp[8]=30;mp[9]=39;mp[10]=47;mp[11]=56;mp[12]=64;mp[13]=38;mp[14]=46;mp[15]=55;mp[16]=63;mp[17]=11;mp[18]=20;mp[19]=28;mp[20]=37;mp[21]=45;mp[22]=54;mp[23]=62;for(short i=1;i<=N;i++){cz[i]=0;ks[i]=0;}cz[9]=cz[23]=1;ks[8]=ks[15]=1;qd=1;zd=12;}return ;}void init(){FZ=1200;cost_water=5;cost_food=10;walk=2;buy=2;dig=3;for(short i=0;i<=Day;i++){for(short j=1;j<=N;j++){for(short w=0;w<=400;w++){for(short f=0;f<=600;f++){if(w*3+f*2<=FZ){dp[i][j][w][f]=-inf;}}}}}for(short k=10;k<=405;k++){for(short l=0;k*3+l*2<=FZ;l++){dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;}}path[0][1][0][0]={0,0,0,0};return ;}int main(){weather={1,1,0,2,0,1,2,0,1,1,2,1,0,1,1,1,2,2,1,1,0,0,1,0,2,1,0,0,1,1,};build_map(2);init();// dp [i][j][w][f]// 第i天在j个点 w 箱水 f 箱食物时最大利润，// max_k_l (dp[30][27][k][l])// 第i天的天气决定 i+1天能否移动// 如：第0天天气决定第1天能否移动// 先不考虑非矿山停留自愿停留情况// for(short i=1;i<N;i++)// {//printf("第%d个点",i);//for(auto j:mp[i]) //{// printf("%d ",j);//}//printf("\n");// }// printf("???%d %d %d %d\n",xh_food[0],xh_food[2],xh_water[0],xh_water[1]);for(short i=0;i<Day;i++){printf("第%d天\n",i);short tq=weather[i];for(short j=1;j<=N;j++){if(cz[j])// 村庄{for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){//购买或不够买物资(ww=0,ff=0就是不购买) if(tq==2) //停留{short money=dp[i][j][w][f];for(short ww=0;ww<=money/cost_water;ww++){for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0){if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food){dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;// path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f};}}}}}else //从j走到jj{for(auto jj:g[j]){short money=dp[i][j][w][f];for(short ww=0;ww<=money/cost_water;ww++){for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++){if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0){if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food){dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;// path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f};}}}}}}}}}else if (ks[j])// 矿山{for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){// 已经停留一天了，可以挖矿if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0){if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0){dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;// path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]+1000};path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f};}}// 在矿山不挖矿或不允许挖矿if(tq==2) //停留但不挖矿{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};}}}else{if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0){for(auto jj:g[j]){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};}}}}}}}else //普通区{for(short w=0;w<=405;w++){for(short f=0;w*3+f*2<=1200;f++){if(tq==2) //在j点停留{if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]){dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};}}}else// 走到jj点{for(auto jj:g[j]){if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0){if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]){dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};}}}}}}}}}short ans=-inf;node lastpath;short last_water=0,last_food=0,last_day=Day;for(short i=0;i<=Day;i++){for(short w=0;w<=405;w++)for(short f=0;w*3+2*f<=1200;f++){if(dp[i][zd][w][f]>ans){ans=dp[i][zd][w][f];lastpath=path[i][zd][w][f];last_water=w;last_food=f;last_day=char(i);}}}stack<node> s;// freopen("outputQ2.txt","w",stdout);printf("ans:%d\n",ans);printf("day:%d weather:%d point:%d water:%d food:%d\n",last_day,weather[Day],zd,last_water,last_food);node temppath=(node){last_day,zd,last_water,last_food};s.push(temppath);while(lastpath!=path[0][1][0][0]){s.push(lastpath);printf("day:%d weather:%d point %d water:%d food:%d\n",lastpath.day,(int)weather[lastpath.day],(int)mp[lastpath.from],lastpath.water,lastpath.food);temppath=lastpath;lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];}}

2.2简化地图+Dijkstra

2.2.1模型简化与分析

游戏原地图较为复杂，但事实上有意义的结点只有起点、终点、村庄和矿山，因此求解时考虑使用Dijkstra，求出这四类结点的最短路径，将原地图压缩到仅包含着四类结点。

下面对各个问题进行讨论与分析

对于只有一名玩家并且每天天气全部已知的情况：第一关和第二关必然有确定的最优解，而地图结构并不复杂，因此可以直接通过穷举、蒙特卡罗等搜索策略求解。

2.2.2模型假设

1.每天的天气情况相互独立。

2.玩家每天早上确定策略，晚上完成状态转移及资源、资金结算。

3.多人游戏中，各个玩家绝对自私、完全理性。

2.2.3 符号说明

2.2.4 模型建立与求解

maxQ30+12pwW30+12pfF30

其中Qt,Wt,Ft分别表示第t天时玩家所剩下的资金、水和食物量。如果玩家在第30天前到达终点，则其各个属性将会在未来几天视作不变，所以我们以第三十天为统一结束时间。该目标函数有如下约束：Qt=Qt−1+QMineMinet−Shopt[2pfShopFt+2pwShopWt]

食物方面

每天结束时的资金等于前一天的资金加上当天挖矿获得的1000元（如果挖矿的话），再减去在村庄购买食物和水花费的钱（如果购买的话）。其中ShopFt和ShopWt分别表示玩家在第t天购买的食物量和水量（如果购买的话）。

Ft=F(t−1)−2Movet △Ft− 3Mine tMovet △Ft−(1−Movet−Minet)△Ft+Shopt ShopFt

水方面

Wt=Wt−1−2Movet△Wt−3Minet△Wt−(1−Movet−Minet)△Wt+ShoptShopWt

2.2.5 地图简化

我们首先引入Dijkstra算法，这是一种在有向赋权图中求两点之间最短路径的高效算法。选取图中起点、终点、村庄和矿山作为特殊点，利用Dijkstra算法计算出每两个特殊点之间的最短路径（即不考虑沙暴天气的影响下，所需最少的天数）。然后根据简化后的情况来完成一幅新的地图。

# encoding: utf-8# init_water=180# init_food=330init_water=184init_food=324money=10000-init_food*10-init_water*5weather=["高温","高温","晴朗","沙暴","晴朗","高温","沙暴","晴朗","高温","高温","沙暴","高温","晴朗","高温","高温","高温","沙暴","沙暴","高温","高温","晴朗","晴朗","高温","晴朗","沙暴","高温","晴朗","晴朗","高温","高温"]base_consume_water=[5,8,10]base_consume_food=[7,6,10]def get_weather(i):if i=="高温":return 1if i=="晴朗":return 0else:return 2def go(hhday,road):already_go=0consume_water=0consume_food=0while already_go<road:if hhday>30:return -1,-1,-1if get_weather(weather[hhday-1])!=2:#print(hhday,"Day go",weather[hhday])consume_food+=base_consume_food[get_weather(weather[hhday-1])]*2consume_water+=base_consume_water[get_weather(weather[hhday-1])]*2hhday+=1already_go+=1else:#print(hhday, "Day dont go")consume_food += base_consume_food[get_weather(weather[hhday-1])]consume_water += base_consume_water[get_weather(weather[hhday-1])]hhday += 1return consume_water,consume_food,hhdaybase_water_price=5base_water_weight=3base_food_price=10base_food_weight=2def possess_c(cur_water,cur_food,cur_money,cur_day,log):can_take=1200-cur_water*3-cur_food*2#print(can_take)#print(cur_money)log=log+"At Day "+str(cur_day)+": "+"Reach c water and food "+str(cur_water)+" "+str(cur_food)+"\n"i=0if cur_day>18:# 准备返程尽可能只携带足以到达终点的物资temp_water=max(36,cur_water)temp_food=max(40,cur_food)i=temp_water-cur_waterj=temp_food-cur_foodtemp_money = cur_money - i* base_water_price * 2-j*base_food_price*2else:# 由于起始点倾向于购买性价比更好的食物，所以这里倾向于购买水已装满背包i=int(can_take/base_water_weight)j=0temp_water=cur_water+itemp_food=cur_foodtemp_money=cur_money-i*base_water_price*2newlog=log+"At Day "+str(cur_day)+": "+"Buy water and food "+str(i)+" "+"\n"q,w,e=go(cur_day,3)temp_water1=temp_water-qtemp_food1=temp_food-wnewlog+="At Day "+str(e)+": "+"Move End water and food "+str(temp_water1)+" "+str(temp_food1)+"\n"possess_z(temp_water1,temp_food1,temp_money,e,newlog)newlog = log+"At Day "+str(cur_day)+": "+"Buy water and food "+str(i)+ "\n"q, w, e = go(cur_day, 2)temp_water2 = temp_water - qtemp_food2 = temp_food - wnewlog += "At Day " + str(e) + ": " + "Move Mine water and food " + str(temp_water2) + " " + str(temp_food2) + "\n"posseess_k(temp_water2, temp_food2, temp_money, e,newlog)log_list={}def possess_z(cur_water,cur_food,cur_money,cur_day,log):#print("END ",cur_water*5/2+cur_food*10/2+cur_money,cur_day)log+="End "+str(cur_day)+" "+str(cur_water*5/2+cur_food*10/2+cur_money)if cur_water<0 or cur_food<0:return -1log_list[log]=cur_water*5/2+cur_food*10/2+cur_moneyreturn cur_water*5/2+cur_food*10/2+cur_moneydef posseess_k(cur_water,cur_food,cur_money,cur_day,log):log = log + "At Day " + str(cur_day) + ": " + "Reach M water and food " + str(cur_water) + " " + str(cur_food) + "\n"water_limit=cur_water/(base_consume_water[get_weather("晴朗")]*3)food_limit=cur_food/(base_consume_food[get_weather("晴朗")]*3)total_limit=int(min(water_limit,food_limit))total_limit=min(total_limit,30-cur_day)for i in range(1,total_limit+1):temp_food=cur_foodtemp_water=cur_watertemp_day=cur_daynewlog=logtemp_money=cur_moneyfor j in range(1,i+1):temp_water=temp_water-base_consume_water[get_weather(weather[cur_day+j-2])]*3temp_food=temp_food-base_consume_food[get_weather(weather[cur_day+j-2])]*3temp_day+=1temp_money+=1000newlog+="At Day " + str(temp_day) + ": " + "Dig " + str(j)+" Days "+str(temp_water) + " " + str(temp_food) +" " + str(temp_money)+ "\n"q, w, e = go(temp_day, 2)if q < 0:continuetemp_water2 = temp_water - qtemp_food2 = temp_food - wif temp_food2 < 0 or temp_water2 < 0:continuenewlog += "At Day " + str(e) + ": " + "Go Village water and food " + str(temp_water2) + " " + str(temp_food2) + "\n"possess_c(temp_water2, temp_food2, temp_money, e, newlog)q,w,e=go(temp_day,5)if q<0:continuetemp_water1=temp_water-qtemp_food1=temp_food-wif temp_food1<0 or temp_water1<0:continuenewlog += "At Day " + str(e) + ": " + "Go end water and food " + str(temp_water1) + " " + str(temp_food1) + "\n"possess_z(temp_water1,temp_food1,temp_money,e,newlog)def check(i,j):if 3*i+2*j>1200 or 5*i+10*j>10000:return Falseelse:return Truedef train():i=0for init_water in range(150,200):for init_food in range(300,360):i+=1if check(init_water, init_food):q,w,e=go(1,6)log=""possess_c(init_water-q,init_food-w,money,e,log)print(i)train()max=-1max_index=0for i in log_list:if log_list[i]>max:max=log_list[i]max_index=iprint(max_index)

3.第三关与第四关

第三关与第四关相比较于前两关，仅仅知道当天的天气，据此决定当天的行动方案，给出最佳策略。

3.1 前两关总结

分析第一关和第二关：可得出以下的基本的策略设计原则

(1)到达终点处的资源恰好耗尽。为了使到达终点的时候资金尽可能的多，万向节没有理由买多余生存需要的水和食物，玩家在七点和村庄购买资源的价格高于终点返还的资金，因此在天气情况已知的情况下，玩家知道维持自己生存所需要的最少资源，所以有能力在到达终点的时候控制资源恰好耗尽。此策略仅仅适用于全局天气已知的情况。第三四关不可以了。

(2)起点处保证生存的情况下多买食物

因为村庄的资源贵，所以尽可能的起点买食物，并且因为背包有上限，所以玩家倾向于在起点购买价格较贵且质量较小的资源。会尽可能的多买食物。