算法设计和分析_最小花费购物问题

1、./ -/ Bussiness.h/ #include #include #include #include class Productpublic:void SetNO(int no)if ( no 999)std:cout wrong NO.;elsem_nNO = no;int GetNO() return m_nNO;void SetPrice(int price)if ( price 999)std:cout wrong price;elsem_nPrice = price;int GetPrice() return m_nPrice;private:intm_nNO;/ 商品编码

2、1,999;int m_nPrice;/ 单独购买的单价 1,999;class Itempublic:void SetNO(int no)if ( no 999)std:cout wrong NO.;elsem_nNO = no;int GetNO() return m_nNO;void SetCount(int count)if ( count 5)std:cout wrong count;elsem_nCount = count;int GetCount() return m_nCount; void SubCount(int nSub) m_nCount -= nSub; privat

3、e:int m_nNO;/ 商品编码 1,999;int m_nCount;/ 购买该商品的个数 1,5;class DiscountTypepublic:int m_nSize;/ 该折扣组合的商品种类数;int * m_pNOs;/ 对应的商品编号;int * m_pCount;/ 对应每种商品需要的个数;int m_nOffer;/ 该种优惠方案所需花销;/int m_nSave;/ 相对于原价节省的钱;intGetProductCount(int nProNO)/ 返回该方案下需要nProNO的个数;int count = 0;/ 一个很大的数超过了单件采购的最高限度;for (int

4、 i = 0; i m_nSize; i+)if (m_pNOsi = nProNO)count = m_pCounti;return count;protected:private:;/ 一次采购的的项目列表;class Purchasepublic:Item *m_pItems;/ 采购的项目列表;intm_nCount;/ 采购的项目数目;void Clone(Purchase & pur)pur.m_nCount = m_nCount;pur.m_pItems = new Itemm_nCount;for (int i = 0; i m_nCount; i+)pur.m_pItemsi

5、 = m_pItemsi;void Clear()delete m_pItems;/ 一家商应该具有的各种商品和促销方案;class Shoppublic:intMinCost(Purchase & curPurchase);Product* m_pProducts;/ 商店里的所有商品;intm_nProTypeCount;/ 商店里所有商品种类的总和;DiscountType * m_pDicounts;/ 商店里的所有促销优惠方案;intm_nDicTypeCount;/ 促销方案的种类;intGetProductPrice(int nProNO);private:intBackspac

6、eMinCost(Purchase & purch, int discTypeID);boolSatisfiedDemand(Purchase & purch, int discTypeID);voidUpdatePurchase(Purchase & purch, int discTypeID);const int MAX_PIECE = 5;const int MAX_PRODUCT_CODE = 999;const int MAX_PURCH_NUM = 5;class ScheduelCostpublic:ScheduelCost();void Init(Shop & theShop,

7、 Purchase & thePurchase);void Comp(int i);void Out();private:void MiniCost();int B;/ 购买物品的数目上限;int S;/ 优惠折扣的类型总数,小于99;int m_costMAX_PIECE+1MAX_PIECE+1MAX_PIECE+1MAX_PIECE+1MAX_PIECE+1;/ 记录了不同的商品总数时的最小花费值;int m_pOffer100MAX_PURCH_NUM+1;int m_pNumMAX_PRODUCT_CODE+1;int m_pProductMAX_PURCH_NUM+1;/ 记录每件

8、采购商品当前的数目;int m_pPurchPieceMAX_PURCH_NUM+1;/ 记录每件采购商品的最大数目;int m_pPurchPriceMAX_PURCH_NUM+1;/ 记录每件采购商品的价格;std:string GetModulePath();bool LoadData(Shop & theShop, Purchase & thePurchase);/ -/ LeastCostPurchase.cpp/ - #include #include #include Bussiness.husing namespace std;int main(int argc, char *

9、 argv)ShoptheShop;PurchasethePurchase;LoadData(theShop, thePurchase);/ 用迭代递归法;int nMinCost = theShop.MinCost(thePurchase);cout 使用迭代调用方法输出最小花费： nMinCost endl;/ 输出数据到文件中;string szOutFilePath = GetModulePath() + LeastCostPurchaseDataoutput.txt;ofstream outfile(szOutFilePath.c_str(), ios:trunc);if (!out

10、file)return -1;outfile 使用迭代调用方法输出最小花费： nMinCost endl;outfile.close();/ 用动态规划法;ScheduelCost dynaScheduel;dynaScheduel.Init(theShop, thePurchase);dynaScheduel.Comp(1);dynaScheduel.Out();system(pause);return 0;int Shop:MinCost(Purchase & curPurchase)int nMin = 100000;int nTempMin = 0;/ 遍历所有的优惠方案;for (i

11、nt i = 0; i nTempMin)nMin = nTempMin;/ 记录下标记;return nMin;intShop:BackspaceMinCost(Purchase & purch, int discTypeID)int nMin = 0;/ 如果购买量能按照该优惠方案给出优惠，返回优惠方案的用度+除去优惠后的剩余商品的MinCost值;if (SatisfiedDemand(purch, discTypeID)Purchase newPurch;purch.Clone(newPurch);/ 更新newPurch;UpdatePurchase(newPurch, discTy

12、peID);/ 迭代求更新后的最小值;nMin = MinCost(newPurch) + m_pDicountsdiscTypeID.m_nOffer;newPurch.Clear();elsefor (int i = 0; i purch.m_nCount; i+)int nPrice = GetProductPrice(purch.m_pItemsi.GetNO();if ( -1 = nPrice)return -1;/有错误;nMin += purch.m_pItemsi.GetCount() * nPrice;return nMin;bool Shop:SatisfiedDeman

13、d(Purchase & purch, int discTypeID)for (int i = 0; i purch.m_nCount; i+)int nProNO = purch.m_pItemsi.GetNO();int nPurCount = purch.m_pItemsi.GetCount();if (nPurCount (m_pDicountsdiscTypeID).GetProductCount(nProNO)return false;/ 只要有一件商品的采购数量不能满足优惠条件，则返回false;return true;void Shop:UpdatePurchase(Purch

14、ase & purch, int discTypeID)for (int i = 0; i purch.m_nCount; i+)int nProNO = purch.m_pItemsi.GetNO();int nSub = (m_pDicountsdiscTypeID).GetProductCount(nProNO);/ 如果该商品在优惠折扣里没有提及，则其为0;purch.m_pItemsi.SubCount(nSub);intShop:GetProductPrice(int nProNO)for (int i = 0; i m_nProTypeCount; i+)if (m_pProdu

15、ctsi.GetNO() = nProNO)return m_pProductsi.GetPrice();return -1;/ 没有找到该商品的价钱则返回-1;bool LoadData(Shop & theShop, Purchase & thePurchase)/ 打开存放数据的文件;string szDataFilePath = GetModulePath() + LeastCostPurchaseDatainput.txt;ifstream infile(szDataFilePath.c_str(); if (!infile)infile.close();return false;/

16、 int nKindsNum = 0;/所购商品种类数, 0 = B nKindsNum;if ( nKindsNum 5)cout 购买的商品总类数太多;return false;Product * pProducts = new ProductnKindsNum;Item * pItems= new ItemnKindsNum;int nRecieve = 0;for (int i = 0 ; i nRecieve;pProductsi.SetNO(nRecieve);/ 商品的编号;pItemsi.SetNO(nRecieve);/ 欲购买的商品的编号;infile nRecieve;p

17、Itemsi.SetCount(nRecieve);infile nRecieve;pProductsi.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文件获得优惠方案;string szOfferFi

18、le = GetModulePath() + LeastCostPurchaseDataoffer.txt;infile.open(szOfferFile.c_str();if (!infile)return false;int nDicTypeCount = 0;infile nDicTypeCount;DiscountType * pDiscounts = new DiscountTypenDicTypeCount;for (int i = 0; i nSize;pDiscountsi.m_nSize = nSize;pDiscountsi.m_pNOs = new intnSize;pD

19、iscountsi.m_pCount = new intnSize;for (int j = 0; j pDiscountsi.m_pNOsj;infile pDiscountsi.m_pCountj;infile pDiscountsi.m_nOffer;infile.close();theShop.m_nDicTypeCount = nDicTypeCount;theShop.m_pDicounts = pDiscounts;pDiscounts= NULL;return true;void ScheduelCost:Init(Shop & theShop, Purchase & theP

20、urchase)B= thePurchase.m_nCount;for (int i = 1; i = B; i+)int code = thePurchase.m_pItemsi-1.GetNO();m_pPurchPiecei = thePurchase.m_pItemsi-1.GetCount();m_pPurchPricei = theShop.m_pProductsi-1.GetPrice();m_pNumcode = i;S = theShop.m_nDicTypeCount;for (int i = 1; i = S; i+)int t = theShop.m_pDicounts

21、i-1.m_nSize;for (int j = 1; j B)MiniCost();return;/ 迭代去遍历（0,0,0,0,0）到(a,b,c,d,e)的各个最小值;for (int j = 0; j = m_pPurchPiecei; j+)m_pProducti = j;/ 依次增加第i种商品的个数;Comp(i+1);/ 去给下一个产品进行个数的设置;void ScheduelCost:MiniCost()int nMinCost = 0;for (int i = 1; i = MAX_PURCH_NUM; i+)nMinCost += (m_pProducti * m_pPur

22、chPricei);int pPreProductMAX_PURCH_NUM+1;for (int t = 1; t = S; t+)bool flag = true;for (int i = 1; i = MAX_PURCH_NUM; i+)pPreProducti = m_pProducti - m_pOfferti;if (pPreProducti 0)flag = false;break;if (flag)int nTempMin = m_costpPreProduct1pPreProduct2pPreProduct3pPreProduct4pPreProduct5 + m_pOffe

23、rt0;if (nTempMin nMinCost)nMinCost = nTempMin;m_costm_pProduct1m_pProduct2m_pProduct3m_pProduct4m_pProduct5 = nMinCost;ScheduelCost:ScheduelCost()/ 记录了不同的商品总数时的最小花费值;for (int i = 0; i = MAX_PIECE; i+)for (int j = 0; j = MAX_PIECE; j+)for (int k = 0; k = MAX_PIECE; k+)for (int m = 0; m = MAX_PIECE; m+)for (int n = 0; n = MAX_PIECE; n+)m_costijkmn = 0;for (int i = 0; i 100; i+)for (int j = 0; j = MAX_PURCH_NUM; j+)m_pOfferij = 0;for (int i = 0; i = MAX_PRODUCT_CODE; i+)m_pNumi = -1;for (int i