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