算法设计和分析最小花费购物问题.docx
- 文档编号:1419192
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:20
- 大小:18.65KB
算法设计和分析最小花费购物问题.docx
《算法设计和分析最小花费购物问题.docx》由会员分享,可在线阅读,更多相关《算法设计和分析最小花费购物问题.docx(20页珍藏版)》请在冰点文库上搜索。
算法设计和分析最小花费购物问题
//----
//Bussiness.h
//
#include
#include
#include
#include
classProduct
{
public:
voidSetNO(intno)
{
if(no<1||no>999)
{
std:
:
cout<<"wrongNO.";
}
else
{
m_nNO=no;
}
}
intGetNO()
{returnm_nNO;}
voidSetPrice(intprice)
{
if(price<1||price>999)
{
std:
:
cout<<"wrongprice";
}
else
{
m_nPrice=price;
}
}
intGetPrice()
{returnm_nPrice;}
private:
intm_nNO;//商品编码[1,999];
intm_nPrice;//单独购买的单价[1,999];
};
classItem
{
public:
voidSetNO(intno)
{
if(no<1||no>999)
{
std:
:
cout<<"wrongNO.";
}
else
{
m_nNO=no;
}
}
intGetNO()
{returnm_nNO;}
voidSetCount(intcount)
{
if(count<1||count>5)
{
std:
:
cout<<"wrongcount";
}
else
{
m_nCount=count;
}
}
intGetCount()
{returnm_nCount;}
voidSubCount(intnSub)
{m_nCount-=nSub;}
private:
intm_nNO;//商品编码[1,999];
intm_nCount;//购买该商品的个数[1,5];
};
classDiscountType
{
public:
intm_nSize;//该折扣组合的商品种类数;
int*m_pNOs;//对应的商品编号;
int*m_pCount;//对应每种商品需要的个数;
intm_nOffer;//该种优惠方案所需花销;
//intm_nSave;//相对于原价节省的钱;
intGetProductCount(intnProNO)//返回该方案下需要nProNO的个数;
{
intcount=0;//一个很大的数超过了单件采购的最高限度;
for(inti=0;i { if(m_pNOs[i]==nProNO) { count=m_pCount[i]; } } returncount; } protected: private: }; //一次采购的的项目列表; classPurchase { public: Item*m_pItems;//采购的项目列表; intm_nCount;//采购的项目数目; voidClone(Purchase&pur) { pur.m_nCount=m_nCount; pur.m_pItems=newItem[m_nCount]; for(inti=0;i { pur.m_pItems[i]=m_pItems[i]; } } voidClear() { delete[]m_pItems; } }; //一家商应该具有的各种商品和促销方案; classShop { public: intMinCost(Purchase&curPurchase); Product*m_pProducts;//商店里的所有商品; intm_nProTypeCount;//商店里所有商品种类的总和; DiscountType*m_pDicounts;//商店里的所有促销优惠方案; intm_nDicTypeCount;//促销方案的种类; intGetProductPrice(intnProNO); private: intBackspaceMinCost(Purchase&purch,intdiscTypeID); boolSatisfiedDemand(Purchase&purch,intdiscTypeID); voidUpdatePurchase(Purchase&purch,intdiscTypeID); }; constintMAX_PIECE=5; constintMAX_PRODUCT_CODE=999; constintMAX_PURCH_NUM=5; classScheduelCost { public: ScheduelCost(); voidInit(Shop&theShop,Purchase&thePurchase); voidComp(inti); voidOut(); private: voidMiniCost(); intB;//购买物品的数目上限; intS;//优惠折扣的类型总数,小于99; intm_cost[MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1];//记录了不同的商品总数时的最小花费值; intm_pOffer[100][MAX_PURCH_NUM+1]; intm_pNum[MAX_PRODUCT_CODE+1]; intm_pProduct[MAX_PURCH_NUM+1];//记录每件采购商品当前的数目; intm_pPurchPiece[MAX_PURCH_NUM+1];//记录每件采购商品的最大数目; intm_pPurchPrice[MAX_PURCH_NUM+1];//记录每件采购商品的价格; }; std: : stringGetModulePath(); boolLoadData(Shop&theShop,Purchase&thePurchase); //----- //LeastCostPurchase.cpp //--- #include #include #include"Bussiness.h" usingnamespacestd; intmain(intargc,char**argv) { ShoptheShop; PurchasethePurchase; LoadData(theShop,thePurchase); //用迭代递归法; intnMinCost=theShop.MinCost(thePurchase); cout<<"使用迭代调用方法输出最小花费: "< //输出数据到文件中; stringszOutFilePath=GetModulePath()+"LeastCostPurchaseData\\output.txt"; ofstreamoutfile(szOutFilePath.c_str(),ios: : trunc); if(! outfile) { return-1; } outfile<<"使用迭代调用方法输出最小花费: "< outfile.close(); //用动态规划法; ScheduelCostdynaScheduel; dynaScheduel.Init(theShop,thePurchase); dynaScheduel.Comp (1); dynaScheduel.Out(); system("pause"); return0; } intShop: : MinCost(Purchase&curPurchase) { intnMin=100000; intnTempMin=0; //遍历所有的优惠方案; for(inti=0;i { nTempMin=BackspaceMinCost(curPurchase,i); if(nMin>nTempMin) { nMin=nTempMin; //记录下标记; } } returnnMin; } intShop: : BackspaceMinCost(Purchase&purch,intdiscTypeID) { intnMin=0; //如果购买量能按照该优惠方案给出优惠,返回优惠方案的用度+除去优惠后的剩余商品的MinCost值; if(SatisfiedDemand(purch,discTypeID)) { PurchasenewPurch; purch.Clone(newPurch); //更新newPurch; UpdatePurchase(newPurch,discTypeID); //迭代求更新后的最小值; nMin=MinCost(newPurch)+m_pDicounts[discTypeID].m_nOffer; newPurch.Clear(); } else { for(inti=0;i { intnPrice=GetProductPrice(purch.m_pItems[i].GetNO()); if(-1==nPrice) { return-1;//有错误; } nMin+=purch.m_pItems[i].GetCount()*nPrice; } } returnnMin; } boolShop: : SatisfiedDemand(Purchase&purch,intdiscTypeID) { for(inti=0;i { intnProNO=purch.m_pItems[i].GetNO(); intnPurCount=purch.m_pItems[i].GetCount(); if(nPurCount<(m_pDicounts[discTypeID]).GetProductCount(nProNO)) { returnfalse;//只要有一件商品的采购数量不能满足优惠条件,则返回false; } } returntrue; } voidShop: : UpdatePurchase(Purchase&purch,intdiscTypeID) { for(inti=0;i { intnProNO=purch.m_pItems[i].GetNO(); intnSub=(m_pDicounts[discTypeID]).GetProductCount(nProNO); //如果该商品在优惠折扣里没有提及,则其为0; purch.m_pItems[i].SubCount(nSub); } } intShop: : GetProductPrice(intnProNO) { for(inti=0;i { if(m_pProducts[i].GetNO()==nProNO) { returnm_pProducts[i].GetPrice(); } } return-1;//没有找到该商品的价钱则返回-1; } boolLoadData(Shop&theShop,Purchase&thePurchase) { //打开存放数据的文件; stringszDataFilePath=GetModulePath()+"LeastCostPurchaseData\\input.txt"; ifstreaminfile(szDataFilePath.c_str()); if(! infile) { infile.close(); returnfalse; } // intnKindsNum=0;//所购商品种类数,0<=B<=5; infile>>nKindsNum; if(nKindsNum<0||nKindsNum>5) { cout<<"购买的商品总类数太多;"; returnfalse; } Product*pProducts=newProduct[nKindsNum]; Item*pItems=newItem[nKindsNum]; intnRecieve=0; for(inti=0;i { infile>>nRecieve; pProducts[i].SetNO(nRecieve);//商品的编号; pItems[i].SetNO(nRecieve);//欲购买的商品的编号; infile>>nRecieve; pItems[i].SetCount(nRecieve); infile>>nRecieve; pProducts[i].SetPrice(nRecieve); } infile.close(); infile.clear(); theShop.m_nProTypeCount=nKindsNum; theShop.m_pProducts=pProducts; pProducts=NULL; thePurchase.m_nCount=nKindsNum; thePurchase.m_pItems=pItems; pItems=NULL; //读入offer.txt文件获得优惠方案; stringszOfferFile=GetModulePath()+"LeastCostPurchaseData\\offer.txt"; infile.open(szOfferFile.c_str()); if(! infile) { returnfalse; } intnDicTypeCount=0; infile>>nDicTypeCount; DiscountType*pDiscounts=newDiscountType[nDicTypeCount]; for(inti=0;i { intnSize=0; infile>>nSize; pDiscounts[i].m_nSize=nSize; pDiscounts[i].m_pNOs=newint[nSize]; pDiscounts[i].m_pCount=newint[nSize]; for(intj=0;j { infile>>pDiscounts[i].m_pNOs[j]; infile>>pDiscounts[i].m_pCount[j]; } infile>>pDiscounts[i].m_nOffer; } infile.close(); theShop.m_nDicTypeCount=nDicTypeCount; theShop.m_pDicounts=pDiscounts; pDiscounts=NULL; returntrue; } voidScheduelCost: : Init(Shop&theShop,Purchase&thePurchase) { B=thePurchase.m_nCount; for(inti=1;i<=B;i++) { intcode=thePurchase.m_pItems[i-1].GetNO(); m_pPurchPiece[i]=thePurchase.m_pItems[i-1].GetCount(); m_pPurchPrice[i]=theShop.m_pProducts[i-1].GetPrice(); m_pNum[code]=i; } S=theShop.m_nDicTypeCount; for(inti=1;i<=S;i++) { intt=theShop.m_pDicounts[i-1].m_nSize; for(intj=1;j<=t;j++) { intcode=theShop.m_pDicounts[i-1].m_pNOs[j-1]; m_pOffer[i][m_pNum[code]]=theShop.m_pDicounts[i-1].m_pCount[j-1]; } m_pOffer[i][0]=theShop.m_pDicounts[i-1].m_nOffer; } } voidScheduelCost: : Comp(inti) { if(i>B) { MiniCost(); return; } //迭代去遍历(0,0,0,0,0)到(a,b,c,d,e)的各个最小值; for(intj=0;j<=m_pPurchPiece[i];j++) { m_pProduct[i]=j;//依次增加第i种商品的个数; Comp(i+1);//去给下一个产品进行个数的设置; } } voidScheduelCost: : MiniCost() { intnMinCost=0; for(inti=1;i<=MAX_PURCH_NUM;i++) { nMinCost+=(m_pProduct[i]*m_pPurchPrice[i]); } intpPreProduct[MAX_PURCH_NUM+1]; for(intt=1;t<=S;t++) { boolflag=true; for(inti=1;i<=MAX_PURCH_NUM;i++) { pPreProduct[i]=m_pProduct[i]-m_pOffer[t][i]; if(pPreProduct[i]<0) { flag=false; break; } } if(flag) { intnTempMin=m_cost[pPreProduct[1]][pPreProduct[2]][pPreProduct[3]][pPreProduct[4]][pPreProduct[5]]+m_pOffer[t][0]; if(nTempMin { nMinCost=nTempMin; } } } m_cost[m_pProduct[1]][m_pProduct[2]][m_pProduct[3]][m_pProduct[4]][m_pProduct[5]]=nMinCost; } ScheduelCost: : ScheduelCost() { //记录了不同的商品总数时的最小花费值; for(inti=0;i<=MAX_PIECE;i++) { for(intj=0;j<=MAX_PIECE;j++) { for(intk=0;k<=MAX_PIECE;k++) { for(intm=0;m<=MAX_PIECE;m++) { for(intn=0;n<=MAX_PIECE;n++) { m_cost[i][j][k][m][n]=0; } } } } } for(inti=0;i<100;i++) { for(intj=0;j<=MAX_PURCH_NUM;j++) { m_pOffer[i][j]=0; } } for(inti=0;i<=MAX_PRODUCT_CODE;i++) { m_pNum[i]=-1; } for(inti=0;i<=MAX_PURCH_NUM;i++) { m_pProduct[i]=0;//记录每件采购商品当前的数目; m_pPurchPiece[i]=0;//记录每件采购商品的最大数目; m_pPurchPrice[i]=0;//记录
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 最小 花费 购物 问题