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

编程入门行业动态更新时间:2024-10-10 12:20:33

【排序和搜索】<a href=https://www.elefans.com/category/jswz/34/1751508.html style= 药店老板的卖药策略"/>

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

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

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

Content

1 题目重现
2 最初的策略
- 2.1 预处理丢弃药品
- 2.2 每日处理过期药品
- 2.3 药品销售策略
- 2.4 药品上架策略
- 2.5 问题
3 重构后的策略
- 3.1 销售策略中的排序
- 3.2 上架策略中的选择
- 3.3 降低算法复杂度
3 实验结果
4 特别鸣谢

1 题目重现

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

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

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

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

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

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

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

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

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

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

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

2 最初的策略

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

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

2.1 预处理丢弃药品

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

⭐哈希函数为 d = H a s h ( k e y ) = k e y d=Hash(key)=key d=Hash(key)=key,其中，key为保质期天数
⭐按照日期遍历哈希表，若在此日期前的所有药品数大于 3 × d a t e 3\times date 3×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天以下 L e s s T h a n T e n LessThanTen LessThanTen,另一个是保质期10天以上 M o r e T h a n T e n MoreThanTen 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天数组，以 P r i c e + M a n a g e F e e Price+ManageFee 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 上架策略中的选择

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