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

// Bussiness.h //

#include #include #include #include

class Product {

public: void SetNO(int no)

{

if ( no < 1 || no > 999) { } else {

std::cout << \"wrong NO.\";

m_nNO = no; } }

int GetNO() { return m_nNO;}

void SetPrice(int price) { if ( price < 1 || price > 999)

{ } else { }

m_nPrice = price; std::cout << \"wrong price\";

}

int GetPrice()

{ return m_nPrice;} private:

int m_nNO; int m_nPrice;

// 商品编码 [1,999]; // 单独购买的单价 [1,999];

};

class Item {

public: };

class DiscountType {

public:

void SetNO(int no) { }

if ( no < 1 || no > 999) { } else { }

m_nNO = no;

std::cout << \"wrong 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; int m_nCount;

// 商品编码 [1,999]; // 购买该商品的个数 [1,5];

int m_nSize; int * m_pNOs; int * m_pCount; int m_nOffer; //int m_nSave;

// 该折扣组合的商品种类数; // 对应的商品编号; // 对应每种商品需要的个数; // 该种优惠方案所需花销; // 相对于原价节省的钱;

// 返回该方案下需要nProNO的个数;

int GetProductCount(int nProNO) {

int count = 0; { }

if (m_pNOs[i] == nProNO) { }

count = m_pCount[i];

// 一个很大的数超过了单件采购的最高限度;

for (int i = 0; i < m_nSize; i++)

return count; } protected: private: };

// 一次采购的的项目列表; class Purchase {

public: Item * };

int

m_pItems; 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

int

GetProductPrice(int nProNO);

MinCost(Purchase & curPurchase); * m_pProducts;

// 商店里的所有商品;

Product int

m_nProTypeCount;

// 商店里所有商品种类的总和;

// 商店里的所有促销优惠方案;

DiscountType * m_pDicounts; int

m_nDicTypeCount; // 促销方案的种类;

private: int };

bool void

BackspaceMinCost(Purchase & purch, int discTypeID);

SatisfiedDemand(Purchase & purch, int discTypeID); 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 Shop::BackspaceMinCost(Purchase & purch, int discTypeID) {

int nMin = 0;

// 如果购买量能按照该优惠方案给出优惠，返回优惠方案的用度+除去优惠后的剩余商if (SatisfiedDemand(purch, discTypeID)) {

Purchase newPurch; purch.Clone(newPurch);

// 更新newPurch;

UpdatePurchase(newPurch, discTypeID); // 迭代求更新后的最小值; 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;

品的MinCost值;

nMin = MinCost(newPurch) + m_pDicounts[discTypeID].m_nOffer;

newPurch.Clear(); } else {

for (int i = 0; i < purch.m_nCount; i++) { }

int nPrice = GetProductPrice(purch.m_pItems[i].GetNO()); if ( -1 == nPrice) { }

nMin += purch.m_pItems[i].GetCount() * nPrice;

return -1;

//有错误;

}

return nMin;

}

bool Shop::SatisfiedDemand(Purchase & purch, int discTypeID) {

for (int i = 0; i < purch.m_nCount; i++) {

int nProNO = purch.m_pItems[i].GetNO();

int nPurCount = purch.m_pItems[i].GetCount();

if (nPurCount < (m_pDicounts[discTypeID]).GetProductCount(nProNO)) {

return false;

// 只要有一件商品的采购数量不能满足优惠条件，

则返回false; } } }

return true;

void Shop::UpdatePurchase(Purchase & purch, int discTypeID) { }

for (int i = 0; i < purch.m_nCount; i++) { }

int nProNO = purch.m_pItems[i].GetNO();

int nSub = (m_pDicounts[discTypeID]).GetProductCount(nProNO); // 如果该商品在优惠折扣里没有提及，则其为0; purch.m_pItems[i].SubCount(nSub);

int Shop::GetProductPrice(int nProNO) { }

bool LoadData(Shop & theShop, Purchase & thePurchase) {

// 打开存放数据的文件;

string szDataFilePath = GetModulePath() + \"LeastCostPurchaseData\\\\input.txt\"; ifstream infile(szDataFilePath.c_str()); if (!infile) { } //

int nKindsNum = 0; infile >> nKindsNum;

//所购商品种类数, 0 <= B <= 5;

infile.close(); return false;

for (int i = 0; i < m_nProTypeCount; i++) { if (m_pProducts[i].GetNO() == nProNO) }

{ }

// 没有找到该商品的价钱则返回-1;

return m_pProducts[i].GetPrice();

return -1;

if ( nKindsNum < 0 || nKindsNum > 5) { cout << \"购买的商品总类数太多;\"; }

return false;

Product * pProducts = new Product[nKindsNum]; Item * pItems = new Item[nKindsNum]; int nRecieve = 0;

for (int i = 0 ; i < nKindsNum; i++) {

infile >> nRecieve;

pProducts[i].SetNO(nRecieve); pItems[i].SetNO(nRecieve); infile >> nRecieve;

pItems[i].SetCount(nRecieve);

// 商品的编号; // 欲购买的商品的编号;

// 读入offer.txt文件获得优惠方案;

string szOfferFile = GetModulePath() + \"LeastCostPurchaseData\\\\offer.txt\"; infile.open(szOfferFile.c_str()); if (!infile) { }

return false;

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;

int nDicTypeCount = 0; infile >> nDicTypeCount;

DiscountType * pDiscounts = new DiscountType[nDicTypeCount]; for (int i = 0; i < nDicTypeCount; i++) { }

int nSize = 0; infile >> nSize;

pDiscounts[i].m_nSize = nSize;

pDiscounts[i].m_pNOs = new int[nSize]; pDiscounts[i].m_pCount = new int[nSize]; for (int j = 0; j < nSize; j++) { }

infile >> pDiscounts[i].m_nOffer;

infile >> pDiscounts[i].m_pNOs[j]; infile >> pDiscounts[i].m_pCount[j];

infile.close();

theShop.m_nDicTypeCount = nDicTypeCount; theShop.m_pDicounts = pDiscounts; pDiscounts = NULL;

return true;

}

void ScheduelCost::Init(Shop & theShop, Purchase & thePurchase) { }

B = thePurchase.m_nCount; for (int i = 1; i <= B; i++) {

int code = 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 (int i = 1; i <= S; i++) { }

int t = theShop.m_pDicounts[i-1].m_nSize; for (int j = 1; j <= t; j++) {

int code = 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;

void ScheduelCost::Comp(int i) { }

void ScheduelCost::MiniCost() { int nMinCost = 0;

if (i > B)

{

MiniCost(); return;

}

// 迭代去遍历（0,0,0,0,0）到(a,b,c,d,e)的各个最小值; for (int j = 0; j <= m_pPurchPiece[i]; j++) { }

m_pProduct[i] = j; Comp(i+1);

// 依次增加第i种商品的个数;

// 去给下一个产品进行个数的设置;

for (int i = 1; i <= MAX_PURCH_NUM; i++) { }

nMinCost += (m_pProduct[i] * m_pPurchPrice[i]);

int pPreProduct[MAX_PURCH_NUM+1]; for (int t = 1; t <= S; t++) {

bool flag = true;

for (int i = 1; i <= MAX_PURCH_NUM; i++) {

pPreProduct[i] = m_pProduct[i] - m_pOffer[t][i]; if (pPreProduct[i] < 0) {

flag = false; break;

} }

if (flag) {

int

nTempMin

= +

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() {

// 记录了不同的商品总数时的最小花费值; 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_cost[i][j][k][m][n] = 0;

for (int i = 0; i < 100; i++) { }

for (int j = 0; j <= MAX_PURCH_NUM; j++) { }

m_pOffer[i][j] = 0;

for (int i = 0; i <= MAX_PRODUCT_CODE; i++) { }

m_pNum[i] = -1;

for (int i = 0; i <= MAX_PURCH_NUM; i++) { m_pProduct[i] = 0; }

m_pPurchPiece[i] = 0; m_pPurchPrice[i] = 0;

// 记录每件采购商品当前的数目; // 记录每件采购商品的最大数目; // 记录每件采购商品的价格;

void ScheduelCost::Out() {

int nMinCost = m_cost[m_pPurchPiece[1]][m_pPurchPiece[2]][m_pPurchPiece[3]][m_pPurchPiece[4]][m_pPurchPiece[5]];

cout << \"使用动态规划方法输出最小花费：\" << nMinCost << endl; // 输出数据到文件中;

string szOutFilePath = GetModulePath() + \"LeastCostPurchaseData\\\\output.txt\"; ofstream outfile(szOutFilePath.c_str(), ios::app); if (!outfile) { return ;

}

}

outfile << \"使用动态规划方法输出最小花费：\" << nMinCost << endl; outfile.close();

////////////////////////////////////////////////////////////////////////// // 获取程序运行目录;// std::string GetModulePath() { }

TCHAR path[256];

//MAX_PATH;

GetModuleFileName(NULL, path, 256); int lastSpilt = 0;

for ( int i = 0; i < 256; i++) {

if (path[i] == '\\\\') { }

lastSpilt = i;

if (path[i] == '\\0') {

break; } }

char * temp = new char[lastSpilt+2]; for (int i = 0 ; i <= lastSpilt; i++) {

temp[i] = path[i]; }

temp[lastSpilt+1] = '\\0'; return temp;