建模穿越沙漠第一问python代码

第一关

import numpy as npqua = np.array((0, 1, 2, 3)) # 4种类型的特殊点：0-> 起点； 1-> 村庄；2 ->矿山; 3-> 终点dist = np.array(((0, 6, 8, 3),(6, 0, 2, 3),(8, 2, 0, 5),(3, 3, 5, 0)))f = np.array(((0, 1, 1, 1), # 判断4中特殊点之间的关系(0, 0, 1, 1),(0, 1, 0, 1),(0, 0, 0, 0)))wea = np.array((2, 2, 1, 3, 1, # 30天内的天气2, 3, 1, 2, 2,3, 2, 1, 2, 2,2, 3, 3, 2, 2,1, 1, 2, 1, 3,2, 1, 1, 2, 2))mx, my = 3, 2 # 水和事物的重量cx, cy = 5, 10 # 水和事物的价格sx = np.array((0, 5, 8, 10)) # 第i种天气的水消耗量sy = np.array((0, 7, 6, 10)) # 第i种天气的食物消耗量n = 4 # 特殊点个数maxm = 1200 # 背包容量coins = 10000 # 初始资金base = 1000 # 基础收益date = 30 # 最晚期限costx = np.zeros((32, 4, 4)) # 第k天从i到j的水消耗量costy = np.zeros((32, 4, 4)) # 第k天从i到j的事食物消耗量days = np.zeros((32, 4, 4), dtype=int) # 第k天从i到j需要多长时间ans = 0 # 最后的资金act = np.empty(32) # 每天的行为：2-> 挖矿；1-> 在矿山休息；0-> 村庄购买食物rec = np.empty(32) # 记录每天在哪里# ansx、ansact记录最优路径上的信息ansx = np.empty(32)ansact = np.empty(32)ansg, ansh = 0, 0 # 记录最优的初始水和食物 def dfs(day: int, now: int, nm: int, c: int, x: int, y: int, type: int) -> None:act[day] = typerec[day] = nowglobal ans, ansg, anshif qua[now] == 3:if ans <= c+x*cx+y*cy:ansg = gansh = hans = c+x*cx+y*cyfor i in range(date+1):ansx[i] = rec[i]ansact[i] = act[i]act[day] = -1rec[day] = -1returnif day >= date:act[day] = -1rec[day] = -1returnif qua[now] == 1:nm = maxm - mx*x - my*yfor i in range(n):if f[qua[now]][qua[i]]:tx = costx[day][now][i]ty = costy[day][now][i]ucost = cum =nmif x >= tx:ux = x - txelse:ux = 0ucost -= 2*(tx-x)*cxum -= (tx - x)*mxif y >= ty:uy = y - tyelse:uy = 0ucost -= 2*(ty - y)*cyum -= (ty - y)*myif ucost < 0 or um < 0:continuedfs(day+days[day][now][i], i, um, ucost, ux, uy, 0)if qua[now] == 2:attday = daytx = sx[wea[attday]]ty = sy[wea[attday]]attday += 1if x > tx:x -= txtx = 0else:tx = tx - xx = 0if y >= ty:y -= tyty = 0else:ty = ty - yy = 0nm -= tx*mx + ty*myc -= 2*tx*cx + 2*ty*cyif nm >= 0 and c >= 0:dfs(attday, now, nm, c, x, y, 1)attday = daytx = sx[wea[attday]]*2ty = sy[wea[attday]]*2attday += 1if x >= tx:x -= txtx = 0else:tx = tx - xx = 0if y >= ty:y -= tyty = 0else:ty = ty -yy = 0nm -= tx*mx + ty*myc -= 2*tx*cx + 2*ty*cyc += baseif nm >= 0 and c >= 0:dfs(attday, now, nm, c, x, y, 2)rec[day] = -1act[day] = -1if __name__ == '__main__':for d in range(date+1):rec[d] = -1act[d] = -1for d in range(date):for i in range(n):for j in range(n):if f[qua[i]][qua[j]]:now, count, sumx, sumy = 0, 0, 0, 0while count < dist[i][j]:if wea[now+d] != 3:count += 1sumx += 2*sx[wea[now+d]]sumy += 2*sy[wea[now+d]]else:sumx += sx[wea[now+d]]sumy += sy[wea[now+d]]now += 1if now + d >= date:breakif count < dist[i][j]:sumx = sumy = 20000now = 30costx[d][i][j] = sumxcosty[d][i][j] = sumydays[d][i][j] = nowprint(type(days[0,0,0]))dic = {}for i in range(maxm+1):g = i // mxh = (maxm-i)//my# print(g, h)dic.setdefault((g,h), 0)if not dic[(g,h)]:print((g,h))dfs(0, 0, 0, coins-g*cx-h*cy, g, h, -1)dic[(g, h)] = 1print(ans)

第二关

import numpy as npqua = np.array((0, 2, 1, 2, 1, 3)) # 4种类型的特殊点：0-> 起点； 1-> 村庄；2 ->矿山; 3-> 终点dist = np.array(((0, 7, 8, 9, 9, 11),(7, 0, 1, 3, 4, 4),(8, 1, 0, 2, 3, 3),(9, 3, 2, 0, 1, 2),(9, 4, 3, 1, 0, 2),(11, 4, 3, 2, 2, 0)))f = np.array(((0, 1, 1, 1), # 判断4中特殊点之间的关系(0, 0, 1, 1),(0, 1, 0, 1),(0, 0, 0, 0)))wea = np.array((2, 2, 1, 3, 1, # 30天内的天气2, 3, 1, 2, 2,3, 2, 1, 2, 2,2, 3, 3, 2, 2,1, 1, 2, 1, 3,2, 1, 1, 2, 2))mx, my = 3, 2 # 水和事物的重量cx, cy = 5, 10 # 水和事物的价格sx = np.array((0, 5, 8, 10)) # 第i种天气的水消耗量sy = np.array((0, 7, 6, 10)) # 第i种天气的食物消耗量n = 6 # 特殊点个数maxm = 1200 # 背包容量coins = 10000 # 初始资金base = 1000 # 基础收益date = 30 # 最晚期限costx = np.zeros((32, 6, 6)) # 第k天从i到j的水消耗量costy = np.zeros((32, 6, 6)) # 第k天从i到j的事食物消耗量days = np.zeros((32, 6, 6), dtype=int) # 第k天从i到j需要多长时间ans = 0 # 最后的资金act = np.empty(32) # 每天的行为：2-> 挖矿；1-> 在矿山休息；0-> 村庄购买食物rec = np.empty(32) # 记录每天在哪里# ansx、ansact记录最优路径上的信息ansx = np.empty(32)ansact = np.empty(32)ansg, ansh = 0, 0 # 记录最优的初始水和食物def dfs(day: int, now: int, nm: int, c: int, x: int, y: int, type: int) -> None:act[day] = typerec[day] = nowglobal ans, ansg, anshif qua[now] == 3:if ans <= c+x*cx+y*cy:ansg = gansh = hans = c+x*cx+y*cyfor i in range(date+1):ansx[i] = rec[i]ansact[i] = act[i]act[day] = -1rec[day] = -1returnif day >= date:act[day] = -1rec[day] = -1returnif qua[now] == 1:nm = maxm - mx*x - my*yfor i in range(n):if f[qua[now]][qua[i]]:tx = costx[day][now][i]ty = costy[day][now][i]ucost = cum =nmif x >= tx:ux = x - txelse:ux = 0ucost -= 2*(tx-x)*cxum -= (tx - x)*mxif y >= ty:uy = y - tyelse:uy = 0ucost -= 2*(ty - y)*cyum -= (ty - y)*myif ucost < 0 or um < 0:continuedfs(day+days[day][now][i], i, um, ucost, ux, uy, 0)if qua[now] == 2:attday = daytx = sx[wea[attday]]ty = sy[wea[attday]]attday += 1if x > tx:x -= txtx = 0else:tx = tx - xx = 0if y >= ty:y -= tyty = 0else:ty = ty - yy = 0nm -= tx*mx + ty*myc -= 2*tx*cx + 2*ty*cyif nm >= 0 and c >= 0:dfs(attday, now, nm, c, x, y, 1)attday = daytx = sx[wea[attday]]*2ty = sy[wea[attday]]*2attday += 1if x >= tx:x -= txtx = 0else:tx = tx - xx = 0if y >= ty:y -= tyty = 0else:ty = ty -yy = 0nm -= tx*mx + ty*myc -= 2*tx*cx + 2*ty*cyc += baseif nm >= 0 and c >= 0:dfs(attday, now, nm, c, x, y, 2)rec[day] = -1act[day] = -1if __name__ == '__main__':for d in range(date+1):rec[d] = -1act[d] = -1for d in range(date):for i in range(n):for j in range(n):if f[qua[i]][qua[j]]:now, count, sumx, sumy = 0, 0, 0, 0while count < dist[i][j]:if wea[now+d] != 3:count += 1sumx += 2*sx[wea[now+d]]sumy += 2*sy[wea[now+d]]else:sumx += sx[wea[now+d]]sumy += sy[wea[now+d]]now += 1if now + d >= date:breakif count < dist[i][j]:sumx = sumy = 20000now = 30costx[d][i][j] = sumxcosty[d][i][j] = sumydays[d][i][j] = nowprint(type(days[0,0,0]))dic = {}for i in range(maxm+1):g = i // mxh = (maxm-i)//my# print(g, h)dic.setdefault((g,h), 0)if not dic[(g,h)]:print((g,h))dfs(0, 0, 0, coins-g*cx-h*cy, g, h, -1)dic[(g, h)] = 1print(ans)