算法设计和分析_最小花费购物问题
- 格式：docx
- 大小：21.96 KB
- 文档页数：13
// ---- // Bussiness.h //
#include #include #include #include
class Product { public: void SetNO(int no) { if ( no < 1 || no > 999) { std::cout << "wrong NO."; } else { m_nNO = no; } } int GetNO() { return m_nNO;}
void SetPrice(int price) { if ( price < 1 || price > 999) { std::cout << "wrong price"; } else { m_nPrice = price; } } int GetPrice() { return m_nPrice;} private: int m_nNO; // 商品编码 [1,999]; int m_nPrice; // 单独购买的单价 [1,999]; }; class Item { public: void SetNO(int no) { if ( no < 1 || no > 999) { std::cout << "wrong NO."; } else { m_nNO = no; } } int GetNO() { return m_nNO;}
void SetCount(int count) { if ( count < 1 || count > 5) { std::cout << "wrong count"; } else { m_nCount = count; } } int GetCount() { return m_nCount; }
void SubCount(int nSub) { m_nCount -= nSub; }
private: int m_nNO; // 商品编码 [1,999]; int m_nCount; // 购买该商品的个数 [1,5]; };
class DiscountType { public: int m_nSize; // 该折扣组合的商品种类数; int * m_pNOs; // 对应的商品编号; int * m_pCount; // 对应每种商品需要的个数; int m_nOffer; // 该种优惠方案所需花销; //int m_nSave; // 相对于原价节省的钱;
int GetProductCount(int nProNO) // 返回该方案下需要nProNO的个数; { int count = 0; // 一个很大的数超过了单件采购的最高限度; for (int i = 0; i < m_nSize; i++) { if (m_pNOs[i] == nProNO) { count = m_pCount[i]; } } return count; } protected: private: };
// 一次采购的的项目列表; class Purchase { public: Item * m_pItems; // 采购的项目列表; int m_nCount; // 采购的项目数目;
void Clone(Purchase & pur) { pur.m_nCount = m_nCount; pur.m_pItems = new Item[m_nCount]; for (int i = 0; i < m_nCount; i++) { pur.m_pItems[i] = m_pItems[i]; } } void Clear() { delete[] m_pItems; } }; // 一家商应该具有的各种商品和促销方案; class Shop { public: int MinCost(Purchase & curPurchase);
Product * m_pProducts; // 商店里的所有商品; int m_nProTypeCount; // 商店里所有商品种类的总和;
DiscountType * m_pDicounts; // 商店里的所有促销优惠方案; int m_nDicTypeCount; // 促销方案的种类;
int GetProductPrice(int nProNO); private: int BackspaceMinCost(Purchase & purch, int discTypeID); bool SatisfiedDemand(Purchase & purch, int discTypeID); void UpdatePurchase(Purchase & purch, int discTypeID);
}; const int MAX_PIECE = 5; const int MAX_PRODUCT_CODE = 999; const int MAX_PURCH_NUM = 5; class ScheduelCost { public: ScheduelCost();
void Init(Shop & theShop, Purchase & thePurchase); void Comp(int i); void Out();
private: void MiniCost();
int B; // 购买物品的数目上限; int S; // 优惠折扣的类型总数,小于99; int m_cost[MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1][MAX_PIECE+1]; // 记录了不同的商品总数时的最小花费值; int m_pOffer[100][MAX_PURCH_NUM+1]; int m_pNum[MAX_PRODUCT_CODE+1]; int m_pProduct[MAX_PURCH_NUM+1]; // 记录每件采购商品当前的数目; int m_pPurchPiece[MAX_PURCH_NUM+1]; // 记录每件采购商品的最大数目; int m_pPurchPrice[MAX_PURCH_NUM+1]; // 记录每件采购商品的价格; };
std::string GetModulePath(); bool LoadData(Shop & theShop, Purchase & thePurchase);
// ----- // LeastCostPurchase.cpp // ---
#include #include #include "Bussiness.h"
using namespace std;
int main(int argc, char ** argv) { Shop theShop; Purchase thePurchase; LoadData(theShop, thePurchase);
// 用迭代递归法; int nMinCost = theShop.MinCost(thePurchase); cout << "使用迭代调用方法输出最小花费：" << nMinCost << endl; // 输出数据到文件中; string szOutFilePath = GetModulePath() + "LeastCostPurchaseData\\output.txt"; ofstream outfile(szOutFilePath.c_str(), ios::trunc); if (!outfile) { 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 (int i = 0; i < m_nDicTypeCount; i++) { nTempMin = BackspaceMinCost(curPurchase, i); if (nMin > nTempMin) { nMin = nTempMin; // 记录下标记; } } return nMin; }
int Shop::BackspaceMinCost(Purchase & purch, int discTypeID) { int nMin = 0; // 如果购买量能按照该优惠方案给出优惠，返回优惠方案的用度+除去优惠后的剩余商品的MinCost值; if (SatisfiedDemand(purch, discTypeID)) { Purchase newPurch; purch.Clone(newPurch); // 更新newPurch; UpdatePurchase(newPurch, discTypeID); // 迭代求更新后的最小值;
