华为云口罩配送大赛经验分享

比赛链接：https://competition.huaweicloud.com/information/1000037176/introduction

赛题分析：

1. 地图大小为12×12，需求点固定为5个，配送目标是将所有需求点的需求进行满足，配送过程中会随机生成捐赠小区
2. 纯命令行交互，使用标准I/O作为命令（S/R/G）和移动方向(E/W/S/N)的传递途径
3. 在1000张地图上测试

思路

1. 我没有做太多的思考，思路也很容易理解，首先先到的就是greedy策略，每次都选择当前最好的选择，当然这只能考虑到局部最优，但最后结果还不错，能排进前二十。
2. 每次配送的时候都优先选择离当前最近的需求点配送，取货的时候给每个捐赠小区一个ranking，就按照捐赠数量/距离来做，试了一下距离的平方结果不如绝对值。
3. 配送有几种情况需要考虑：
   • 车上口罩为0，那么肯定要去取货，那么就按ranking来选择
   • 车上口罩为100，那么肯定要去送货，就选择最近的，因为最远的周边可能后续会生成捐赠小区
   • 接下的两种情况最难考虑，就是送完一个小区或者刚取完一些车上还剩，那么是去接着送别的小区，还是取货呢？我的想法就是也写一个ranking比较，送货和取货的价值比较，但要考虑一些特殊情况，如果此时的货够最近的需求小区a那么就去送，如果此时的货加上离aranking最高的取货点足够那么就直接去取货点取货，当然这考虑非常不够，很需要改进,可以学习依一下别的选手的思路。

代码分析

下面对我的代码进行讲解，用python写的.
load:当前装载量
target：目标地
R(字典)：对应坐标的货量，需求点就是负值，捐赠和仓库就是正值，坐标要用元组，不是列表

主函数

需求小区仓库初始化

python

if __name__ == '__main__':
    new_string=input()
    s_list=new_string.split()
    S=(int(s_list[1]),int(s_list[2]))
    R={}
    R[(int(s_list[1]),int(s_list[2]))]=100
    for i in range(0,5):
        new_string=input()
        r_list=new_string.split()
        R[(int(r_list[1]),int(r_list[2]))]=int(r_list[3])
    p=list(S)
    load=0             #初始化装载量为0
    target=S

选择（每次到达小区或者捐赠点就行下一步的选择)

这里我加入了一个配送时如果有顺路的捐赠小区，那就去取一下

python

while True:
        P=tuple(p)
        if P == S:
            load = 100
            target = choose_na_target(p)
        elif P in R.keys():
            sum=load+R[P]
            if R[P] < 0:
                if sum<0:
                    load=0
                    R[P]=sum
                    if R[closest(p)] >= -R[P]:
                        target = closest(p)
                    else:
                        target= choose_target(p)        #车空就去送取货
                else:
                    del R[P]
                    if len(R)==0:
                        break
                    if min(R.values())>0:
                        break
                    load=sum
                    target1 = choose_na_target(p)
                    target2 = choose_target(p)
                    target3 = choose_target(target1)
                    if load >= -R[target1]: 
                        target = target1
                    elif load + R[target3] >= -R[target1]:
                        target = target3
                    else:
                        target =  com_value(p ,target1,target2)
            else:
                if sum > 100:
                    load=100
                    R[P]=sum-100
                    target = choose_na_target(p)
                else:
                    del R[P]
                    load=sum
                    target1 = choose_na_target(p)
                    target2 = choose_target(p)
                    if load >= -R[target1]: 
                        target = target1
                    else:
                        target =  com_value(p ,target1,target2)
            for k in R.keys():																#顺路就去取
                if R[k] > 0:
                    if(k[0]>=target[0] and  k[0]<=p[0]) or (k[0]<=target[0] and  k[0]>=p[0]):
                        if(k[1]>=target[1] and  k[1]<=p[1]) or (k[1]<=target[1] and  k[1]>=p[1]):
                            target = k

读取命令行输入

python

new_string=input()
        if new_string=='G':          #读取到行动的命令，向target移动
            p,next_step=step(p,target)
            print(next_step)
        else:
            r_list=new_string.split()
            if p[0] == int(r_list[1]) and p[1] == int(r_list[2]):                   #空投贴脸hhh
                if load + int(r_list[3]) <= 100:
                    load = load + int(r_list[3])
                else:
                    R[(int(r_list[1]),int(r_list[2]))]=int(r_list[3])-100+load
                    load = 100
            else:
                R[(int(r_list[1]),int(r_list[2]))]=int(r_list[3])           #更新一下选择
                if  R[target] > 0:     #注意R里没有S
                    target = choose_target(p)
                else:
                    cur_target = (int(r_list[1]),int(r_list[2]))
                    target = com_value(p ,target,cur_target)

移动函数

python

def step(pos,to):
    if pos[0]<to[0]:
        pos[0]=pos[0]+1
        return pos,'S'
    elif pos[0]>to[0]:
        pos[0]=pos[0]-1
        return pos,'N'
    else:
        if pos[1]<to[1]:
            pos[1]=pos[1]+1
            return pos,'E'
        else:
            pos[1]=pos[1]-1
            return pos,'W'

选择捐赠小区和需求小区

python

def choose_na_target(pos):
    na_distance=0
    global load
    for k in R.keys():
        if R[k] < 0:
            if k[0]==pos[0] and k[1]==pos[1]:
                continue
            cur_dis2 = 1/ (abs(pos[0]-k[0])+abs(pos[1]-k[1])+1)
            if cur_dis2 > na_distance:
                na_distance = cur_dis2
                tar = k
    return tar

```python

def choose_target(pos):
    po_distance=0
    global load
    distance = (100-load)/ (abs(pos[0]-S[0])+abs(pos[1]-S[1])+1)
    for k in R.keys():
        if R[k] > 0:
            if k[0]==pos[0] and k[1]==pos[1]:
                continue
            if R[k] + load > 100:
                cur_dis1 = (100-load)/ (abs(pos[0]-k[0])+abs(pos[1]-k[1])+1)
            else:
                cur_dis1 = R[k] / (abs(pos[0] - k[0]) + abs(pos[1] - k[1])+1)
            if cur_dis1 > po_distance:
                po_distance = cur_dis1
                tar =k   
    if  po_distance> distance:
        return tar 
    else:
        return S

捐赠小区和需求小区的比较ranking

python

def com_value(pos,target1,target2):
    global target
    if load < -R[target1]:
        cur_value1 = load
    else: 
        cur_value1 = -R[target1]
    value1 = cur_value1 / (abs(pos[0]-target1[0])+abs(pos[1]-target1[1])+1)
    if load +R[target2] > 100:
        cur_value2 = 100 -load
    else: 
        cur_value2 = R[target2]
    value2 = cur_value2 / (abs(pos[0]-target2[0])+abs(pos[1]-target2[1])+1)
    if value1 >value2:
        return target1
    else:
        return target2