【排序和搜索】药店老板的卖药策略

对比上一个银行实验来说，这次实验的难度，是更考验大家的编程能力的👩‍🔬
因为这次，所有的代码从零开始！所有的策略都要自己去想qwq)

不过，这篇文章我主要想聊一聊策略，因为我的程序没有任何高级算法【大概就是你希望的那种算法，可以依据不同的条件去迭代调节策略，但很不幸，短时间内我写不出来😢】，所以我完全是按照策略找一些合适的数据结构和基础到不行的排序、搜索算法来实现的，不过收益还不错。此刻让我们高呼数学yyds!!
这里强推一位大佬的退火算法！！戳戳！

1 题目重现

你是一家药店的老板，这个月你从供货商手里收到了一批共50个药品，

√ 其中每个药品有独立的进价和保质期，其中进价的区间为[20,30]元，保质期的剩余天数为[1,15]天

√ 你每天可以陈列出10个药品在商店中售卖，每天会有三个顾客各过来购买一个药品。

√ 药品的定价只能为商品进价加上【-1.5,-1, -0.5, 0, 2 ,4 ,6】元，不得随意定价。

√ 每位顾客购买的逻辑是，买其中最便宜的药品，如果说最便宜的药品价格一致则购买保质期长的药品。

√ 三位顾客会依次购买药品。

√ 药品如果没有陈列在商店中，而是存放在仓库时，会收取管理费，其中保质期低于5天的每天收取1元管理费，其余的每天收取0.5元。

√ 你的目标是，10天之后，你的利润（售出商品售价总和-售出商品进价总和-支付仓库的管理费用-10天内过期/丢弃商品的进价）最大。

不知道各位看到这道题目的感想是什么，我当时看到这个题目的时候，笑容突然凝固了呢 =）

老师非常温馨地提醒了我们：不要想暴力枚举所有的情况哟~

因为去年我们的某位学长就把所有的情况列了一遍。验收的时候，“老师，你看我开始跑了哈”【40分钟过去了】“老师我跑好啦！” 所以说，大力出奇迹这句话在哪里都能用上

2 最初的策略

我把策略分为以下几个部分，分别来讲一讲

1. 预处理必须要丢弃的药品
2. 每日处理过期药品
3. 药品售卖策略
4. 药品上架策略

2.1 预处理丢弃药品

仓库存放药品选取的数据结构为：哈希表

⭐哈希函数为$d=Hash(key)=key$,其中，key为保质期天数
⭐按照日期遍历哈希表，若在此日期前的所有药品数大于$3\times date$,则删去其中价格最低的药品。

//To delet the medicine which have to be discarded absolutely
void Pre_Process(WH*w,ofstream &del)//delete the node which is impossible to save.
{int d=1;int counts=0;char ID[3];for(d=1;d<10;d++){counts+=w->map->data[d].count;   if(counts>3*(d)){for(int x=counts-3*d;x>0;x--){ElementType who=*GetWhoDelet(w->map,d);HashNodeDel(w,who.id,who.day);itoa(who.id,ID,10);del<<'0'<<'\t'<<ID<<'\n';w->gross-=who.price;w->num--;counts--;}}}w->ln=0;w->num=0;
}
//Get Which Medicine to be deleted
ElementType *GetWhoDelet(HashMap *mp,int day)
{ElementType * who=(ElementType*)malloc(sizeof(ElementType));who=PutOn(*mp->data[1].cur);for(int i=1;i<=day;i++){if(mp->data[i].stat==Empty){continue;}ElementType *temp=PutOn(*mp->data[i].cur);while(temp){if(Larger(*who,*temp)){who=PutOn(*temp);    }temp=temp->next;}}return who;
}

2.2 每日处理过期药品

防止某些步骤中有疏漏，每天要按照药品的保质期和日期进行保护处理，以达到题目要求

⭐在此之前，已经将哈希表中的药品按照保质期分为了两个数组，一个是保质期10天以下$LessThanTen$,另一个是保质期10天以上$MoreThanTen$
⭐因为只模拟10天，只可能在第一个数组中出现过期药品

void Fix(WH *w,int date,int n,ofstream &del)
{for(int i=0;i<n;i++){if((w->LessThanTen[i].day-date)<0 && (w->LessThanTen[i].id!=-1)){char day[3];char ID[3];itoa(date,day,10);itoa(w->LessThanTen[i].id,ID,10);del<<day<<"\t"<<ID<<"\n";w->gross-=w->LessThanTen[i].price;//HashNodeDel(w,w->LessThanTen[i].id,w->LessThanTen[i].day);w->ln--;w->LessThanTen[i].id=-1;w->num--;}}
}

2.3 药品销售策略

如何确定药品的销售顺序，是策略中的重点之一。在最初的策略里，我一直在想同时顾及到保质期和进价，得出以下的一些想法
⭐ 针对保质期小于10天数组，以$Price+ManageFee$为关键码进行降序排序，将序号大于30的丢弃。
⭐针对保质期大于等于10天数组，以Price为关键码进行降序排序
⭐定性的来看，这种处理方法可以使得不好卖的又比较便宜的提前扔掉，少一点管理费；但实际上，这会导致保质期比较短的本来可以用策略卖出去，但提前被扔掉，亏损会增加
⭐排序算法：快速排序

void OrderLess(WH*w,int n)
{QSort3(w->LessThanTen,0,n);float min=w->LessThanTen[0].price;int index;if(n>=30){for(int i=30;i<=n;i++){for(int j=0;j<n;j++){if(w->LessThanTen[j].id!=-1 && w->LessThanTen[j].price<min){index=j;break;}}HashNodeDel(w,w->LessThanTen[index].id,w->LessThanTen[index].day);w->LessThanTen[index].id=-1;w->gross-=w->LessThanTen[index].price;}}
}void OrderMore(WH*w,int n)
{QSort33(w->MoreThanTen,0,n);
}

2.4 药品上架策略

这个策略非常重要！它关系到一个重要的成本问题，就是管理费！

⭐ 药品上架：从LessThanTen中按顺序上架，尽可能使得按照顺序每天都卖出三个指定药品。前三个id非-1的药品作为当日要卖的药品，若货架没有补齐，按照一定规则先上架理论上不影响前三个药品上架的药品，直到货架堆满为止；当小于10天的药品卖完之后，大于10天的药品中选取保质期相对短的上架，以减少管理费的产生。

⭐上架规则：前三个药品的最高原始进价为标准线，后续药品按加6元后比标准线高的，予以理论上架可能。之后，对于后7个药品进行以定价为关键码的从低到高排序。排序完成后，针对7-10每一个药品，计算在它存在时，前三个药品能够定价多少，若计算出此时的利润小于 18-(后续药品管理费)，将该药品下架。(示意图如下)

tips:当货架上所有药品均为保质期大于10天时，不需要做此步骤，只需在10个药品中找到价格最低的3个药品进行售卖即可

2.5 问题

眼看就到了ddl前的最后一个晚上，谁能想到去年教辅的策略那么佛系(只要我的策略够烂，同学们就都能满分 )，今年教辅的策略还算挺不错，赚的钱还真多。我连夜修改代码，一整个重构了所有的排序和上架原则，人类的潜能真是无穷无尽【反正就很神奇，很多看似完不成的任务，找不出的bug，改不好的代码，最后都能做好，只要你一直做:)

我和教辅的受益差的不是一点半点，一整个就在亏钱…就是我前面提到的销售策略和上架策略，没有抓住主要矛盾，顾虑太多旁支末节，导致反而亏本。

3 重构后的策略

重构的策略主要就在三个方面
⭐销售策略中的排序
⭐上架策略中的选择
⭐降低算法复杂度

3.1 销售策略中的排序

⭐排序关键码改为：保质期(小于10天数组)，进价(大于等于10天数组)

//For the MoreThanTen Array
void QSort33(ElementType A[],int low, int high)
{int i,j;int k,l;ElementType temp,empty;for(k=0;k<=high;k++){if(A[k].id==-1){empty=A[k];for(l=k;l<high;l++){A[l]=A[l+1];}A[l]=empty;high--;k--;}}if(low>=high) return;i=low;j=high;temp=A[SelectPivot_fix(&A,low,high)];while(i<j){while(i<j && A[j].price<temp.price)j--;//Less(A[j],temp)if(i<j){A[i]=A[j];i++;}while(i<j  && A[i].price>=temp.price)i++;//Largerequal(A[i],temp)if(i<j){A[j]=A[i];j--;}}A[i]=temp;QSort33(A,low,j-1);QSort33(A,j+1,high);
}//for the LessThanTen Array
void QSort3(ElementType A[],int low, int high)
{int i,j;int k,l;ElementType temp,empty;for(k=0;k<=high;k++){if(A[k].id==-1){empty=A[k];for(l=k;l<high;l++){A[l]=A[l+1];}A[l]=empty;high--;k--;}}if(low>=high) return;i=low;j=high;temp=A[SelectPivot_fix(&A,low,high)];while(i<j){while(i<j && (A[j].day>temp.day || (A[j].day==temp.day && A[j].price>temp.price)))j--;//Less(A[j],temp)if(i<j){A[i]=A[j];i++;}while(i<j  && (A[j].day<temp.day || (A[j].day==temp.day && A[j].price<temp.price)))i++;//Largerequal(A[i],temp)if(i<j){A[j]=A[i];j--;}}A[i]=temp;QSort3(A,low,j-1);QSort3(A,j+1,high);
}

3.2 上架策略中的选择

⭐当$LessThanTen$数组中的药还没卖完时，在其中选取7个药品(管理费为1元的优先)进行上架(且价格上不能影响3个药品的售卖)，用来节约管理费
⭐当$LessThanTen$数组卖完了但还没结束时，$MoreThanTen$数组按照保质期长短先后上架(为了节约管理费)，后面7个药品(管理费1元的优先)，以不影响药品售卖的原则按数组顺序上架(数组内已经按价格降序排过了)

这一段代码我写的不好，大家可以按照这个思路用自己的风格实现√

3.3 降低算法复杂度

那个编译器吧，像是有什么大饼，复杂度高一点的地方它就给你判断成死循环，就给你中断运行了。但其实你用单步调试完全🆗。当你遇到这种问题的时候，一定要去检查自己的算法，是不是有多余的循环、遍历、搜索过程，把这些进行简化

我自己因为用了哈希表作为一个存储结构，一开始在卖药过程中我会对哈希表进行节点的删除，为了表示药品已经被卖出或者丢弃。但这就导致要对哈希表进行非常多次的遍历、删除操作，算法复杂度过高。

在进行上面这些操作的时候，我忽略了自己已经把药品分类放在了两个数组里，这俩数组的规模并不大。

所以，我通过把卖掉或丢弃的药品id置为-1，减少了数组删除元素的复杂度$O(n)$,只要每次使用时记得加上 $id!=-1$的判断条件即可。

经过这样类似的一番修改，终于还算是成功的做了个药店，它能赚钱啦！

3 实验结果

一个晚上的极限修改，让我从几乎每个数据集亏本，到每个数据集赚的都不少，这之中策略的决策真的十分重要。

4 特别鸣谢

特别感谢哆啦B梦同学的大力支持，虽然表面上说着

不知道不知道，自己想去

但是，还是花费了宝贵的一个小时跟我讨论这个题目的数学策略，让我能完全理清思路，也为我一个晚上重构代码奠定了深厚的基础.让我们再次高呼

数 学 ，y y d s !

题外话：不得不说我写代码真的很烂，别人几百行写完的我怎么就要写上千呢…不过这个实验好歹是做完了🎉