数学建模2020B题穿越沙漠

这篇具有很好参考价值的文章主要介绍了数学建模2020B题穿越沙漠。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.题目

考虑如下的小游戏:玩家凭借一张地图,利用初始资金购买一定数量的水和食物(包括食品和其他日常用品),从起点出发,在沙漠中行走。途中会遇到不同的天气,也可在矿山、村庄补充资金或资源,目标是在规定时间内到达终点,并保留尽可能多的资金。
游戏的基本规则如下:
(1)以天为基本时间单位,游戏的开始时间为第0天,玩家位于起点。玩家必须在截止日期或之前到达终点,到达终点后该玩家的游戏结束。
(2)穿越沙漠需水和食物两种资源,它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽,视为游戏失败。
(3)每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一,沙漠中所有区域的天气相同。
(4)每天玩家可从地图中的某个区域到达与之相邻的另一个区域,也可在原地停留。沙暴日必须在原地停留。
(5)玩家在原地停留一天消耗的资源数量称为基础消耗量,行走一天消耗的资源数量为基础消耗量的倍。
(6)玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点,但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物,每箱退回价格为基准价格的一半。
(7)玩家在矿山停留时,可通过挖矿获得资金,挖矿一天获得的资金量称为基础收益。如果挖矿,消耗的资源数量为基础消耗量的倍;如果不挖矿,消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
(8)玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物,每箱价格为基准价格的2倍。
请根据游戏的不同设定,建立数学模型,解决以下问题。

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

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时:

  1. 第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
  1. 非沙暴天气:
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 j
    int 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 j
    short 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 符号说明

数学建模2020B题穿越沙漠

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算法计算出每两个特殊点之间的最短路径(即不考虑沙暴天气的影响下,所需最少的天数) 。然后根据简化后的情况来完成一幅新的地图。
数学建模2020B题穿越沙漠

# encoding: utf-8
# init_water=180
# init_food=330
init_water=184
init_food=324
money=10000-init_food*10-init_water*5


weather=["高温","高温","晴朗","沙暴","晴朗",
         "高温","沙暴","晴朗","高温","高温",
         "沙暴","高温","晴朗","高温","高温",
         "高温","沙暴","沙暴","高温","高温",
         "晴朗","晴朗","高温","晴朗","沙暴",
         "高温","晴朗","晴朗","高温","高温"
         ]

base_consume_water=[5,8,10]
base_consume_food=[7,6,10]

def get_weather(i):
    if i=="高温":
        return 1
    if i=="晴朗":
        return 0
    else:
        return 2

def go(hhday,road):

    already_go=0
    consume_water=0
    consume_food=0
    while already_go<road:
        if hhday>30:
            return -1,-1,-1
        if get_weather(weather[hhday-1])!=2:
            #print(hhday,"Day go",weather[hhday])
            consume_food+=base_consume_food[get_weather(weather[hhday-1])]*2
            consume_water+=base_consume_water[get_weather(weather[hhday-1])]*2
            hhday+=1
            already_go+=1
        else:
            #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 += 1
    return consume_water,consume_food,hhday

base_water_price=5
base_water_weight=3
base_food_price=10
base_food_weight=2

def 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=0
    if cur_day>18:
        # 准备返程 尽可能只携带足以到达终点的物资
        temp_water=max(36,cur_water)
        temp_food=max(40,cur_food)
        i=temp_water-cur_water
        j=temp_food-cur_food
        temp_money = cur_money - i* base_water_price * 2-j*base_food_price*2
    else:
        # 由于起始点倾向于购买性价比更好的食物,所以这里倾向于购买水已装满背包
        i=int(can_take/base_water_weight)
        j=0
        temp_water=cur_water+i
        temp_food=cur_food
        temp_money=cur_money-i*base_water_price*2

    newlog=log+"At Day "+str(cur_day)+": "+"Buy water and food "+str(i)+" "+"\n"
    q,w,e=go(cur_day,3)
    temp_water1=temp_water-q
    temp_food1=temp_food-w
    newlog+="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 - q
    temp_food2 = temp_food - w
    newlog += "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 -1
    log_list[log]=cur_water*5/2+cur_food*10/2+cur_money
    return cur_water*5/2+cur_food*10/2+cur_money

def 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_food
        temp_water=cur_water
        temp_day=cur_day
        newlog=log
        temp_money=cur_money

        for j in range(1,i+1):
            temp_water=temp_water-base_consume_water[get_weather(weather[cur_day+j-2])]*3
            temp_food=temp_food-base_consume_food[get_weather(weather[cur_day+j-2])]*3
            temp_day+=1
            temp_money+=1000
            newlog+="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:
            continue
        temp_water2 = temp_water - q
        temp_food2 = temp_food - w

        if temp_food2 < 0 or temp_water2 < 0:
            continue
        newlog += "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:
            continue
        temp_water1=temp_water-q
        temp_food1=temp_food-w


        if temp_food1<0 or temp_water1<0:
            continue

        newlog += "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 False
    else:
        return True

def train():
    i=0
    for init_water in range(150,200):
        for init_food in range(300,360):
            i+=1
            if 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=-1
max_index=0
for i in log_list:
    if log_list[i]>max:
        max=log_list[i]
        max_index=i
print(max_index)

3.第三关与第四关

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

3.1 前两关总结

分析第一关和第二关:可得出以下的基本的策略设计原则
(1)到达终点处的资源恰好耗尽。为了使到达终点的时候资金尽可能的多,万向节没有理由买多余生存需要的水和食物,玩家在七点和村庄购买资源的价格高于终点返还的资金,因此在天气情况已知的情况下,玩家知道维持自己生存所需要的最少资源,所以有能力在到达终点的时候控制资源恰好耗尽。此策略仅仅适用于全局天气已知的情况。第三四关不可以了。
(2)起点处保证生存的情况下多买食物
因为村庄的资源贵,所以尽可能的起点买食物,并且因为背包有上限,所以玩家倾向于在起点购买价格较贵且质量较小的资源。会尽可能的多买食物。

3.2 三关

第三关和第四关由于存在随机性,不能够给出一个确定性的最优策略,所以在设计方案之后需要对方案的结果进行评价
沿用动态规划的思想的情况下处理第三关
第三关天气是随机的。但是地图比较小且只有10天,所有天气一供1024中情况,可以利用动态规划给出每一种情况的最优解,用统计的方法来观察规律。
通过观察最优解策略,发现即使在全部晴天状态下也没有全部去挖矿,可以猜想这一关不能挖矿。
事实上,由于第三关没有村庄,又因为高温天气消耗更大,且挖矿收益更小,即使在晴朗的天气挖矿,收益仅为200-165=35,挖矿五天的收益175还不能弥补绕路造成的资源损耗。所以直接去终点是比较正确的选择。

3.3四关

分析第四关之于以前的关卡引入一个新的概念决策点。这个决策点13距离起点只有4天的路程,而且是玩家在沙漠中的必经点,这和第三关的情况非常相似。同时决策点距离村庄和矿山都只有一天的行程,在决策点的装屯点直接影响了玩家的决策,因此是玩家做决策的关键点。
分析一般情况下最有策略
地图中没有矿山和村庄的情况

当玩家距离下一个目的地较近的时候,玩家不应该等待,应该尽可能的到达目的地,因为更长时间的停留会大大的增加资源的消耗,甚至会失败的风险,即使等待最终能够到达终点,最后的资金和快速通过的方案也相差无几,通过避开高温行走而节省的金钱并不多。
地图中有村庄和矿山的情况
出发点的策略是携带效率高的资源,在村庄大量补充携带资源效率低的资源
行动策略为在接近村庄和矿山的点进行决策,若资源较少则先去补充资源,若资源较多就去挖矿,当挖矿挖到资源剩余按最坏的打算仅够前往下一个功能点的时候。

3.4 如何处理天气

处理天气的思路一种情况是上面提到到按照一定分布随机生成,然后统计每一种情况分析出最有的策略。
还有一种是利用马尔可夫链,建立了天气预测而模型。根据第一关天气转换情况预测其余关卡的天气情况,在根据问题一的模型得出在不同天气情况下玩家的最佳策略,利用对应的天气情况概率和最佳策略下的最大资金,可以得出最终收益的数学期望,选择数学期望最大的一种策略

4.使用软件与编程语言

按照解决问题的不同思路使用不同的工具;
如果是使用动态规划作为主要求解的方法,那么C++,MATLAB都可以作为求解的办法。
如果侧重于仿真与模拟,通过蒙特卡洛这种方法来求解。可以使用Python来完成。
如果是使用groubi等求解器,可以配合MATLAB和编程语言一起使用。

本文第二部分动态规划解决第一二关的代码来源于

https://www.cnblogs.com/cherrypill/p/15158527.html文章来源地址https://www.toymoban.com/news/detail-419766.html

到了这里,关于数学建模2020B题穿越沙漠的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数学建模】历年全国大学生数学建模竞赛题目+定位分析

    数学建模 https://so.csdn.net/so/search?q=%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1spm=1001.2101.3001.7020 国赛创办于1992年,每年一届,是首批列入“高校学科竞赛排行榜”的19项竞赛之一。2020年,来自全国及美国、英国、马来西亚的1470所院校/校区、45680队(本科41826队、专科3854队)、13万多人报名参赛

    2024年02月06日
    浏览(86)
  • 2022天府杯国际赛数学建模题目和思路

    下面是翻译过的,并非原题目。原题下载链接: https://wwp.lanzouv.com/iQWok0e9amcd 2022天府国际数模思路代码在线编写文档: https://docs.qq.com/doc/DRnRJYXBWYXBXYXhN

    2024年02月13日
    浏览(55)
  • 2023高教杯数学建模1:ABC题目+初步想法

    马上参加华为杯研数学建模了hh,找一下数模逻辑 看看今年本科有什么题目,随手记录下思路 附件数据: result2.xlsx 可尝试方法 如果有条件(代码有一定难度),可以尝试 启发式算法 ,如模拟退火、蚁群算法、遗传算法等,适用于非线性和非凸问题 如果不行,下面的方法也

    2024年02月09日
    浏览(64)
  • 全国大学生数学建模竞赛【高教杯】- 竞赛题目汇总

    目录 1992 年赛题 A 题 施肥效果分析 B 题 实验数据分解 1993 年赛题

    2024年02月07日
    浏览(52)
  • 数学建模四大模型、历年国赛题目以及优秀论文

          2021年数学建模国赛马上就要开始了(2021年9月9日)目前数学建模国赛培训已经进入火热的备战时期,许多高校早已开始了数学建模的线上培训。而且因为疫情的原因,数学建模国赛是线上不受影响,但一些线下的大型比赛被推迟,如电子设计竞赛国赛等,小编就是因为

    2024年02月16日
    浏览(51)
  • 2020年数维杯数学建模C题 垃圾转运优化模型设计求解全过程文档及程序

    原题再现:    随着我国人口的不断增加及城镇化进程的快速推进,城市面临了众多公共管理方面的难题。如生活垃圾、废气废水及排泄物等等的处理问题。截止2019年底我国拥有十多个千万规模以上的大型城市,城镇人口数量达到了8.48亿人。    数据统计结果表明我国的

    2024年02月07日
    浏览(44)
  • 2020年华数杯数学建模B题工业零件切割优化方案设计求解全过程文档及程序

    原题再现:    在大型工业产品中,如机床、轮船、飞机,常常需要很多的小零件,如螺钉、螺帽、螺栓、活塞等。在零件的生产过程中,第一步是需要依照零件产品尺寸从原材料中截取初级产品,这是零件制造的第一道工序。在这道工序中,不同的截取方案具有不同的材

    2024年02月05日
    浏览(55)
  • 数学建模论文写作学习——论文题目、关键词、摘要写作学习

    目录 一、论文题目 二、 三、摘要内容(具有独立性、代表性) 第一部分:摘要前言 第二部分:摘要正文 ①简述问题 ②建模思路(一定写关键步骤,不要写思维引导) ③模型求解 ④结果分析(联系赛题) 第三部分:摘要结尾 ①应尽量涵盖论文研究的主要对象或研

    2024年02月08日
    浏览(64)
  • 2021 年数学建模竞赛题目D 题 连铸切割的在线优化

          在满足基本要求和正常要求的条件下,依据尾坯长度制定出最优的 切割方案。假定用户目标值为 9.5 米,目标范围为 9.0~10.0 米,对以下尾坯长 度:109.0、93.4、80.9、72.0、62.7、52.5、44.9、42.7、31.6、22.7、14.5 和 13.7(单位:米),按“尾坯长度、切割方案、切割损失”等

    2024年02月11日
    浏览(77)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包