1.題目
考慮如下的小游戲：玩家憑借一張地圖，利用初始資金購(gòu)買(mǎi)一定數(shù)量的水和食物（包括食品和其他日常用品），從起點(diǎn)出發(fā)，在沙漠中行走。途中會(huì)遇到不同的天氣，也可在礦山、村莊補(bǔ)充資金或資源，目標(biāo)是在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。
游戲的基本規(guī)則如下：
（1）以天為基本時(shí)間單位，游戲的開(kāi)始時(shí)間為第0天，玩家位于起點(diǎn)。玩家必須在截止日期或之前到達(dá)終點(diǎn)，到達(dá)終點(diǎn)后該玩家的游戲結(jié)束。
（2）穿越沙漠需水和食物兩種資源，它們的最小計(jì)量單位均為箱。每天玩家擁有的水和食物質(zhì)量之和不能超過(guò)負(fù)重上限。若未到達(dá)終點(diǎn)而水或食物已耗盡，視為游戲失敗。
（3）每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區(qū)域的天氣相同。
（4）每天玩家可從地圖中的某個(gè)區(qū)域到達(dá)與之相鄰的另一個(gè)區(qū)域，也可在原地停留。沙暴日必須在原地停留。
（5）玩家在原地停留一天消耗的資源數(shù)量稱(chēng)為基礎(chǔ)消耗量，行走一天消耗的資源數(shù)量為基礎(chǔ)消耗量的倍。
（6）玩家第0天可在起點(diǎn)處用初始資金以基準(zhǔn)價(jià)格購(gòu)買(mǎi)水和食物。玩家可在起點(diǎn)停留或回到起點(diǎn)，但不能多次在起點(diǎn)購(gòu)買(mǎi)資源。玩家到達(dá)終點(diǎn)后可退回剩余的水和食物，每箱退回價(jià)格為基準(zhǔn)價(jià)格的一半。
（7）玩家在礦山停留時(shí)，可通過(guò)挖礦獲得資金，挖礦一天獲得的資金量稱(chēng)為基礎(chǔ)收益。如果挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量的倍；如果不挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量。到達(dá)礦山當(dāng)天不能挖礦。沙暴日也可挖礦。
（8）玩家經(jīng)過(guò)或在村莊停留時(shí)可用剩余的初始資金或挖礦獲得的資金隨時(shí)購(gòu)買(mǎi)水和食物，每箱價(jià)格為基準(zhǔn)價(jià)格的2倍。
請(qǐng)根據(jù)游戲的不同設(shè)定，建立數(shù)學(xué)模型，解決以下問(wèn)題。
- 假設(shè)只有一名玩家，在整個(gè)游戲時(shí)段內(nèi)每天天氣狀況事先全部已知，試給出一般情況下玩家的最優(yōu)策略。求解附件中的“第一關(guān)”和“第二關(guān)”，并將相應(yīng)結(jié)果分別填入Result.xlsx。
- 假設(shè)只有一名玩家，玩家僅知道當(dāng)天的天氣狀況，可據(jù)此決定當(dāng)天的行動(dòng)方案，試給出一般情況下玩家的最佳策略，并對(duì)附件中的“第三關(guān)”和“第四關(guān)”進(jìn)行具體討論。
2.解題思路與第一關(guān)與第二關(guān)
有三大種思路
1.動(dòng)態(tài)規(guī)劃
2.簡(jiǎn)略地圖后使用Dijkstra算法來(lái)解決
3.分析題干然后建立模型利用groubi,lingo求解最優(yōu)解
2.1 動(dòng)態(tài)規(guī)劃情況
設(shè)狀態(tài)dp[k][j][w][f]代表第k天時(shí)在第j個(gè)點(diǎn)剩余水為w箱剩余食物為f箱的最大資金，則：
ans=MAXw,f,i dp[k][zd][w][f]
2.1.1 初始值設(shè)定
由于起始點(diǎn)可以在起點(diǎn)購(gòu)買(mǎi)物資，則有初始狀態(tài)
dp[0][qd][w][f]=10000?cost_water?w?cost_food?fw∈[0,400]f∈[0,600]
其中cost_water??，cost_food???? 為購(gòu)買(mǎi)水和食物消耗的錢(qián)。
這里假設(shè)起始為第0天，則第一天天氣影響的是從第0天到第1天。
2.1.2 狀態(tài)轉(zhuǎn)移方程
當(dāng)?shù)趉天人在村莊j時(shí)：
- 第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
當(dāng)?shù)趉天人在礦山j(luò)時(shí)：
挖礦
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])
當(dāng)?shù)趉天人在其他地區(qū)時(shí)
第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思考隱含條件約束模型
除了回村莊補(bǔ)充物資，不會(huì)走回頭路。
除了挖礦和沙塵暴不會(huì)在原地停留。
只會(huì)走關(guān)鍵點(diǎn)之間的最短路徑
2.1.4代碼
第一關(guān)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
// 點(diǎn)數(shù)
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++)
{
//購(gòu)買(mǎi)或不夠買(mǎi)物資(ww=0,ff=0就是不購(gòu)買(mǎi))
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走到j(luò)j
{
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++)
{
// 已經(jīng)停留一天了，可以挖礦
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 //普通區(qū)
{
for(int w=0;w<=405;w++)
{
for(int f=0;w*3+f*2<=1200;f++)
{
if(tq==2) //在j點(diǎn)停留
{
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// 走到j(luò)j點(diǎn)
{
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;
}
第二關(guān)
#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個(gè)點(diǎn) w 箱水 f 箱食物 時(shí)最大利潤(rùn)，
// max_k_l (dp[30][27][k][l])
// 第i天的天氣決定 i+1天能否移動(dòng)
// 如：第0天天氣決定第1天能否移動(dòng)
// 先不考慮非礦山停留自愿停留情況
// for(short i=1;i<N;i++)
// {
// printf("第%d個(gè)點(diǎn)",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++)
{
//購(gòu)買(mǎi)或不夠買(mǎi)物資(ww=0,ff=0就是不購(gòu)買(mǎi))
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走到j(luò)j
{
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++)
{
// 已經(jīng)停留一天了，可以挖礦
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 //普通區(qū)
{
for(short w=0;w<=405;w++)
{
for(short f=0;w*3+f*2<=1200;f++)
{
if(tq==2) //在j點(diǎn)停留
{
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// 走到j(luò)j點(diǎn)
{
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簡(jiǎn)化地圖+Dijkstra
2.2.1模型簡(jiǎn)化與分析
游戲原地圖較為復(fù)雜，但事實(shí)上有意義的結(jié)點(diǎn)只有起點(diǎn)、終點(diǎn)、村莊和礦山，因此求解時(shí)考慮使用Dijkstra，求出這四類(lèi)結(jié)點(diǎn)的最短路徑，將原地圖壓縮到僅包含著四類(lèi)結(jié)點(diǎn)。
下面對(duì)各個(gè)問(wèn)題進(jìn)行討論與分析
對(duì)于只有一名玩家并且每天天氣全部已知的情況：第一關(guān)和第二關(guān)必然有確定的最優(yōu)解，而地圖結(jié)構(gòu)并不復(fù)雜，因此可以直接通過(guò)窮舉、蒙特卡羅等搜索策略求解。
2.2.2模型假設(shè)
1.每天的天氣情況相互獨(dú)立。
2.玩家每天早上確定策略，晚上完成狀態(tài)轉(zhuǎn)移及資源、資金結(jié)算。
3.多人游戲中，各個(gè)玩家絕對(duì)自私、完全理性。
2.2.3 符號(hào)說(shuō)明
2.2.4 模型建立與求解
maxQ30+12pwW30+12pfF30
其中Qt,Wt,Ft分別表示第t天時(shí)玩家所剩下的資金、水和食物量。如果玩家在第30天前到達(dá)終點(diǎn)，則其各個(gè)屬性將會(huì)在未來(lái)幾天視作不變，所以我們以第三十天為統(tǒng)一結(jié)束時(shí)間。該目標(biāo)函數(shù)有如下約束：Qt=Qt?1+QMineMinet?Shopt[2pfShopFt+2pwShopWt]
食物方面
每天結(jié)束時(shí)的資金等于前一天的資金加上當(dāng)天挖礦獲得的1000元（如果挖礦的話），再減去在村莊購(gòu)買(mǎi)食物和水花費(fèi)的錢(qián)（如果購(gòu)買(mǎi)的話）。其中ShopFt和ShopWt分別表示玩家在第t天購(gòu)買(mǎi)的食物量和水量（如果購(gòu)買(mǎi)的話）。
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 地圖簡(jiǎn)化
我們首先引入Dijkstra算法，這是一種在有向賦權(quán)圖中求兩點(diǎn)之間最短路徑的高效算法。選取圖中起點(diǎn)、終點(diǎn)、村莊和礦山作為特殊點(diǎn)，利用Dijkstra算法計(jì)算出每?jī)蓚€(gè)特殊點(diǎn)之間的最短路徑（即不考慮沙暴天氣的影響下，所需最少的天數(shù)） 。然后根據(jù)簡(jiǎn)化后的情況來(lái)完成一幅新的地圖。
# 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:
# 準(zhǔn)備返程 盡可能只攜帶足以到達(dá)終點(diǎn)的物資
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:
# 由于起始點(diǎn)傾向于購(gòu)買(mǎi)性?xún)r(jià)比更好的食物，所以這里傾向于購(gòu)買(mǎi)水已裝滿背包
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.第三關(guān)與第四關(guān)
第三關(guān)與第四關(guān)相比較于前兩關(guān)，僅僅知道當(dāng)天的天氣，據(jù)此決定當(dāng)天的行動(dòng)方案，給出最佳策略。
3.1 前兩關(guān)總結(jié)
分析第一關(guān)和第二關(guān)：可得出以下的基本的策略設(shè)計(jì)原則
(1)到達(dá)終點(diǎn)處的資源恰好耗盡。為了使到達(dá)終點(diǎn)的時(shí)候資金盡可能的多，萬(wàn)向節(jié)沒(méi)有理由買(mǎi)多余生存需要的水和食物，玩家在七點(diǎn)和村莊購(gòu)買(mǎi)資源的價(jià)格高于終點(diǎn)返還的資金，因此在天氣情況已知的情況下，玩家知道維持自己生存所需要的最少資源，所以有能力在到達(dá)終點(diǎn)的時(shí)候控制資源恰好耗盡。此策略?xún)H僅適用于全局天氣已知的情況。第三四關(guān)不可以了。
(2)起點(diǎn)處保證生存的情況下多買(mǎi)食物
因?yàn)榇迩f的資源貴，所以盡可能的起點(diǎn)買(mǎi)食物，并且因?yàn)楸嘲猩舷?，所以玩家傾向于在起點(diǎn)購(gòu)買(mǎi)價(jià)格較貴且質(zhì)量較小的資源。會(huì)盡可能的多買(mǎi)食物。
3.2 三關(guān)
第三關(guān)和第四關(guān)由于存在隨機(jī)性，不能夠給出一個(gè)確定性的最優(yōu)策略，所以在設(shè)計(jì)方案之后需要對(duì)方案的結(jié)果進(jìn)行評(píng)價(jià)
沿用動(dòng)態(tài)規(guī)劃的思想的情況下處理第三關(guān)
第三關(guān)天氣是隨機(jī)的。但是地圖比較小且只有10天，所有天氣一供1024中情況，可以利用動(dòng)態(tài)規(guī)劃給出每一種情況的最優(yōu)解，用統(tǒng)計(jì)的方法來(lái)觀察規(guī)律。
通過(guò)觀察最優(yōu)解策略，發(fā)現(xiàn)即使在全部晴天狀態(tài)下也沒(méi)有全部去挖礦，可以猜想這一關(guān)不能挖礦。
事實(shí)上，由于第三關(guān)沒(méi)有村莊，又因?yàn)楦邷靥鞖庀母螅彝诘V收益更小，即使在晴朗的天氣挖礦，收益僅為200-165=35，挖礦五天的收益175還不能彌補(bǔ)繞路造成的資源損耗。所以直接去終點(diǎn)是比較正確的選擇。
3.3四關(guān)
分析第四關(guān)之于以前的關(guān)卡引入一個(gè)新的概念決策點(diǎn)。這個(gè)決策點(diǎn)13距離起點(diǎn)只有4天的路程，而且是玩家在沙漠中的必經(jīng)點(diǎn)，這和第三關(guān)的情況非常相似。同時(shí)決策點(diǎn)距離村莊和礦山都只有一天的行程，在決策點(diǎn)的裝屯點(diǎn)直接影響了玩家的決策，因此是玩家做決策的關(guān)鍵點(diǎn)。
分析一般情況下最有策略
地圖中沒(méi)有礦山和村莊的情況
當(dāng)玩家距離下一個(gè)目的地較近的時(shí)候，玩家不應(yīng)該等待，應(yīng)該盡可能的到達(dá)目的地，因?yàn)楦L(zhǎng)時(shí)間的停留會(huì)大大的增加資源的消耗，甚至?xí)〉娘L(fēng)險(xiǎn)，即使等待最終能夠到達(dá)終點(diǎn)，最后的資金和快速通過(guò)的方案也相差無(wú)幾，通過(guò)避開(kāi)高溫行走而節(jié)省的金錢(qián)并不多。
地圖中有村莊和礦山的情況
出發(fā)點(diǎn)的策略是攜帶效率高的資源，在村莊大量補(bǔ)充攜帶資源效率低的資源
行動(dòng)策略為在接近村莊和礦山的點(diǎn)進(jìn)行決策，若資源較少則先去補(bǔ)充資源，若資源較多就去挖礦，當(dāng)挖礦挖到資源剩余按最壞的打算僅夠前往下一個(gè)功能點(diǎn)的時(shí)候。
3.4 如何處理天氣
處理天氣的思路一種情況是上面提到到按照一定分布隨機(jī)生成，然后統(tǒng)計(jì)每一種情況分析出最有的策略。
還有一種是利用馬爾可夫鏈，建立了天氣預(yù)測(cè)而模型。根據(jù)第一關(guān)天氣轉(zhuǎn)換情況預(yù)測(cè)其余關(guān)卡的天氣情況，在根據(jù)問(wèn)題一的模型得出在不同天氣情況下玩家的最佳策略，利用對(duì)應(yīng)的天氣情況概率和最佳策略下的最大資金，可以得出最終收益的數(shù)學(xué)期望，選擇數(shù)學(xué)期望最大的一種策略
4.使用軟件與編程語(yǔ)言
按照解決問(wèn)題的不同思路使用不同的工具；
如果是使用動(dòng)態(tài)規(guī)劃作為主要求解的方法，那么C++,MATLAB都可以作為求解的辦法。
如果側(cè)重于仿真與模擬，通過(guò)蒙特卡洛這種方法來(lái)求解?？梢允褂肞ython來(lái)完成。
如果是使用groubi等求解器，可以配合MATLAB和編程語(yǔ)言一起使用。
本文第二部分動(dòng)態(tài)規(guī)劃解決第一二關(guān)的代碼來(lái)源于文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-419766.html
https://www.cnblogs.com/cherrypill/p/15158527.html文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-419766.html
到了這里，關(guān)于數(shù)學(xué)建模2020B題穿越沙漠的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
