当前位置: 代码迷 >> 综合 >> 编程之美之买书问题
  详细解决方案

编程之美之买书问题

热度:51   发布时间:2024-01-17 14:57:31.0

这个问题来自《编程之美》这本书,应该在微软面试中出现过。是一个典型的动态规划问题。

问题描述
《哈利波特》系列一共有五卷,每一卷售价均8欧元。同时买不同的卷(各一本)有折扣,具体如下表所示。

购买方案 折扣
2卷 5%
3卷 10%
4卷 20%
5卷 25%
在一份订单中,根据购买的卷数及本数,可以有多种不同折扣规则。但一本书只能应用一个折扣规则。
设计一个算法,计算购书组合,使得所购买的一批书花费最少。

求解及分析
假设输入为:1本卷1,2本卷2,2本卷3,2本卷4,1本卷5
购买组合及其折扣
5*0.25+3*0.1=1.55
4*0.2+4*0.2=1.6
3*0.1+3*0.1+2*0.05=0.7
2*0.05+2*0.05+2*0.05+2*0.05=0.4
可以看出最优组合为4+4时折扣最大。

程序描述
IDE:vs2010
语言:c++
工程:win32控制台程序

基本程序文件
数据结构定义文件:CommonDefine.h

#pragma once
#include <vector>
#include <string>
#include <map>using namespace std;//定义书籍信息
struct StBookInfo
{StBookInfo(): strVolIdx(""), nBookCount(0){}string strVolIdx;//卷描述int nBookCount;//书数bool operator<(const StBookInfo& bookInfo) const{return nBookCount < bookInfo.nBookCount;}bool operator>(const StBookInfo& bookInfo) const{return nBookCount > bookInfo.nBookCount;}
};typedef vector<StBookInfo> VctBookInfo;struct StBuyPlan
{double dbOff;//折扣值vector<string> vBuyBooks;//购买书籍列表
};typedef vector<StBuyPlan> VctBuyPlan;
算法采用策略模式,定义一个统一接口IBuyMethod.h。

#pragma once
#include "CommonDefine.h"class IBuyMethod
{
public:virtual ~IBuyMethod() {}/*@brief 购买书籍方法@param[in] vBookList 待购买列表@param[out] vBuyPlan 购买折扣及组合*/virtual void BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan) = 0;
};

对应运行类CBookBuy。

BookBuy.h

#pragma once
#include "IBuyMethod.h"class CBookBuy
{
public:CBookBuy(void);~CBookBuy(void);void Run();private:void InitBookList();private:IBuyMethod* m_pMethod;vector<StBookInfo> m_vBookList;
};
BookBuy.cpp

#include "StdAfx.h"
#include "BookBuy.h"
#include "GreedyBuy.h"
#include "DynPrgBuy.h"
#include "DynPrgBuyM.h"
#include <iostream>using namespace std;CBookBuy::CBookBuy(void)
{//算法采用了策略模式,方便随时替换m_pMethod = new CGreedyBuy();//m_pMethod = new CDynPrgBuy();//m_pMethod = new CDynPrgBuyM();InitBookList();
}CBookBuy::~CBookBuy(void)
{delete m_pMethod;m_pMethod = NULL;m_vBookList.clear();
}void CBookBuy::Run()
{VctBuyPlan vBuyPlan;m_pMethod->BuyBook(m_vBookList, vBuyPlan);double dbTotalOff = 0;VctBuyPlan::iterator vPlanIter = vBuyPlan.begin();for (; vPlanIter != vBuyPlan.end(); ++vPlanIter){double dbCurOff = vPlanIter->dbOff;int nCurCount = (int)vPlanIter->vBuyBooks.size();double dbSubOff = dbCurOff*nCurCount;dbTotalOff += dbSubOff;cout<<"当前折扣:"<<dbSubOff<<"="<<dbCurOff<<"*"<<nCurCount;cout<<"\t购买组合:";vector<string>::iterator vBookIter = vPlanIter->vBuyBooks.begin();for (; vBookIter != vPlanIter->vBuyBooks.end(); ++vBookIter){cout<<(*vBookIter)<<" ";}cout<<endl;}cout<<"总的折扣:"<<dbTotalOff<<endl;
}void CBookBuy::InitBookList()
{StBookInfo bookInfo;bookInfo.strVolIdx = "卷1";bookInfo.nBookCount = 1;m_vBookList.push_back(bookInfo);bookInfo.strVolIdx = "卷2";bookInfo.nBookCount = 2;m_vBookList.push_back(bookInfo);bookInfo.strVolIdx = "卷3";bookInfo.nBookCount = 2;m_vBookList.push_back(bookInfo);bookInfo.strVolIdx = "卷4";bookInfo.nBookCount = 2;m_vBookList.push_back(bookInfo);bookInfo.strVolIdx = "卷5";bookInfo.nBookCount = 1;m_vBookList.push_back(bookInfo);
}

可以调用来运行
CBookBuy buyTool;
buyTool.Run();

贪心算法
直观上想,每步都取折扣最大的组合,这样可以实现贪心算法。

GreedyBuy.h

#pragma once
#include "IBuyMethod.h"//贪心购买算法
class CGreedyBuy : public IBuyMethod
{
public:CGreedyBuy(void);virtual ~CGreedyBuy(void);virtual void BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan);private://移除已空的书籍void RemoveEmptyBook(VctBookInfo& vBookList);
};
GreedyBuy.cpp

#include "StdAfx.h"
#include "GreedyBuy.h"CGreedyBuy::CGreedyBuy(void)
{
}CGreedyBuy::~CGreedyBuy(void)
{
}void CGreedyBuy::BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan)
{VctBookInfo vInputBook = vBookList;//贪心算法,确保当前步获取为最优值double dbTotalSum = 0;while (true){RemoveEmptyBook(vInputBook);if (vInputBook.empty()){break;}int nVolCount = 0;vector<string> vCurBooks;VctBookInfo::iterator vIter = vInputBook.begin();for (; vIter != vInputBook.end(); ++vIter){++nVolCount;--vIter->nBookCount;vCurBooks.push_back(vIter->strVolIdx);}double dbOff = 0;switch (nVolCount){case 2: dbOff = 0.05; break;case 3: dbOff = 0.10; break;case 4: dbOff = 0.20; break;case 5: dbOff = 0.25; break;}StBuyPlan planInfo;planInfo.dbOff = dbOff;planInfo.vBuyBooks = vCurBooks;vBuyPlan.push_back(planInfo);}
}void CGreedyBuy::RemoveEmptyBook(VctBookInfo& vBookList)
{VctBookInfo::iterator vIter = vBookList.begin();for (; vIter != vBookList.end();){if (vIter->nBookCount > 0){++vIter;}else{vIter = vBookList.erase(vIter);}}
}

  运行结果如下
  当前折扣:1.25=0.25*5   购买组合:卷1 卷2 卷3 卷4 卷5
  当前折扣:0.3=0.1*3     购买组合:卷2 卷3 卷4
  总的折扣:1.55
  
  最大折扣为1.6,贪婪算法得到的结果并不是最优的。
  
基本动态规划
  每卷的价格都一样,故算法可做简化。
  F为总折扣率。
  输入Y为每卷的书数。

其中Y1,Y2,Y3,Y4,Y5根据大小做过排序,Y1>Y2>Y3>Y4>Y5。
  F(Y1,Y2,Y3,Y4,Y5)
  = 0 if (Y1=Y2=Y3=Y4=Y5=0)
  = max{
  5*0.25+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1), if (Y5>=1)
  4*0.20+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5), if (Y4>=1)
  3*0.10+F(Y1-1,Y2-1,Y3-1,Y4,Y5), if (Y3>=1)
  2*0.05+F(Y1-1,Y2-1,Y3,Y4,Y5), if (Y2>=1)
  1*0+F(Y1-1,Y2,Y3,Y4,Y5), if (Y1>=1)
  }
  动态规划,获取最大的折扣。
  
  例:
  F(1,2,2,2,1)
  = max{
  5*0.25+F(0,1,1,1,0),
  4*0.20+F(0,1,1,1,1),
  3*0.10+F(0,1,1,2,1),
  2*0.05+F(0,1,2,2,1),
  1*0+F(0,2,2,2,1),
  }
  //等价于,排序结果
  = max{
  5*0.25+F(1,1,1,0,0),
  4*0.20+F(1,1,1,1,0),
  3*0.10+F(2,1,1,1,0),
  2*0.05+F(2,2,1,1,0),
  1*0+F(2,2,2,1,0),
  }

源码DynPrgBuy.h。

#pragma once
#include "IBuyMethod.h"//动态规划算法求解
class CDynPrgBuy : public IBuyMethod
{
public:CDynPrgBuy(void);~CDynPrgBuy(void);virtual void BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan);private:double BuyByDyn(VctBookInfo vBookList, VctBuyPlan& vBuyPlan);//移除已空的书籍void RemoveEmptyBook(VctBookInfo& vBookList);
};
DynPrgBuy.cpp

#include "StdAfx.h"
#include "DynPrgBuy.h"
#include <algorithm>using namespace std;CDynPrgBuy::CDynPrgBuy(void)
{
}CDynPrgBuy::~CDynPrgBuy(void)
{
}void CDynPrgBuy::BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan)
{BuyByDyn(vBookList, vBuyPlan);
}//动态规划求最优的问题
double CDynPrgBuy::BuyByDyn(VctBookInfo vBookList, VctBuyPlan& vBuyPlan)
{RemoveEmptyBook(vBookList);if (vBookList.empty()){return 0;}//对书本个数从大到小排列sort(vBookList.begin(), vBookList.end(), greater<StBookInfo>());static int s_count = 0;++s_count;cout<<s_count<<endl;map<double, VctBuyPlan> mapBuyPlan;int nBookCount = (int)vBookList.size();for (int i = nBookCount; i >=1; i--){int nBuyCount = i;VctBookInfo vTempList = vBookList;//计算当前所有的折扣double dbOff = 0;switch (nBuyCount){case 1: dbOff = 0; break;case 2: dbOff = 0.05; break;case 3: dbOff = 0.10; break;case 4: dbOff = 0.20; break;case 5: dbOff = 0.25; break;}StBuyPlan buyPlan;buyPlan.dbOff = dbOff;for (int j = 0; j < nBuyCount; j++){StBookInfo& bkInfo = vTempList[j];--bkInfo.nBookCount;buyPlan.vBuyBooks.push_back(bkInfo.strVolIdx);}//计算左折扣double dbLeftOff = dbOff*nBuyCount;//计算右折扣,需递归VctBuyPlan vTempPlan;vTempPlan.push_back(buyPlan);double dbRightOff = BuyByDyn(vTempList, vTempPlan);//当前购买方式折扣double dbCurOff = dbLeftOff + dbRightOff;//折扣与组合方式映射mapBuyPlan.insert(make_pair(dbCurOff, vTempPlan));}if (mapBuyPlan.empty()){return 0;}//取所有折扣中的最大值//利用map特性取最后一个值即为最大值map<double, VctBuyPlan>::iterator mBigPos = mapBuyPlan.end();--mBigPos;vBuyPlan.insert(vBuyPlan.end(), mBigPos->second.begin(), mBigPos->second.end());return mBigPos->first;
}void CDynPrgBuy::RemoveEmptyBook(VctBookInfo& vBookList)
{VctBookInfo::iterator vIter = vBookList.begin();for (; vIter != vBookList.end();){if (vIter->nBookCount > 0){++vIter;}else{vIter = vBookList.erase(vIter);}}
}
  运行结果如下。
当前折扣:0.8=0.2*4     购买组合:卷2 卷3 卷4 卷1
当前折扣:0.8=0.2*4     购买组合:卷2 卷3 卷4 卷5
总的折扣:1.6
循环体执行了124次
由于采用了递归,时间复杂度太高,这是一个指数级的算法。

改进动态规划
仔细分析可以发现,递归算法中重复执行了很多步骤。
比如F(1,2,2,2,1)中包含F(1,1,1,0,0)求解,我们将这个值做下缓存。当再次需要F(1,1,1,0,0)值时,直接从缓存中获取即可。
DynPrgBuyM.h

#pragma once
#include "IBuyMethod.h"//动态规划算法求解
class CDynPrgBuyM : public IBuyMethod
{
public:CDynPrgBuyM(void);~CDynPrgBuyM(void);virtual void BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan);private:double BuyByDyn(VctBookInfo vBookList, VctBuyPlan& vBuyPlan);void BuyAllGroup(const VctBookInfo& vBookList, map<double, VctBuyPlan>& mapBuyPlan);//移除已空的书籍void RemoveEmptyBook(VctBookInfo& vBookList);CString GetBuyKey(const VctBookInfo& vBookList);private:map<CString, map<double, VctBuyPlan>> m_BuyMap;//加载一个缓存来提高计算效率
};
DynPrgBuyM.cpp

#include "StdAfx.h"
#include "DynPrgBuyM.h"
#include <algorithm>using namespace std;CDynPrgBuyM::CDynPrgBuyM(void)
{
}CDynPrgBuyM::~CDynPrgBuyM(void)
{
}void CDynPrgBuyM::BuyBook(const VctBookInfo& vBookList, VctBuyPlan& vBuyPlan)
{BuyByDyn(vBookList, vBuyPlan);
}//动态规划求最优的问题
double CDynPrgBuyM::BuyByDyn(VctBookInfo vBookList, VctBuyPlan& vBuyPlan)
{RemoveEmptyBook(vBookList);if (vBookList.empty()){return 0;}//对书本个数从大到小排列sort(vBookList.begin(), vBookList.end(), greater<StBookInfo>());map<double, VctBuyPlan> mapBuyPlan;CString strBuyKey = GetBuyKey(vBookList);map<CString, map<double, VctBuyPlan>>::iterator mFindPos = m_BuyMap.find(strBuyKey);if (mFindPos != m_BuyMap.end()){mapBuyPlan = mFindPos->second;}else{static int s_count = 0;++s_count;cout<<s_count<<endl;BuyAllGroup(vBookList, mapBuyPlan);m_BuyMap.insert(make_pair(strBuyKey, mapBuyPlan));}if (mapBuyPlan.empty()){return 0;}//取所有折扣中的最大值//利用map特性取最后一个值即为最大值map<double, VctBuyPlan>::iterator mBigPos = mapBuyPlan.end();--mBigPos;vBuyPlan.insert(vBuyPlan.end(), mBigPos->second.begin(), mBigPos->second.end());return mBigPos->first;
}void CDynPrgBuyM::BuyAllGroup(const VctBookInfo& vBookList, map<double, VctBuyPlan>& mapBuyPlan)
{int nBookCount = (int)vBookList.size();for (int i = nBookCount; i >=1; i--){int nBuyCount = i;VctBookInfo vTempList = vBookList;//计算当前所有的折扣double dbOff = 0;switch (nBuyCount){case 1: dbOff = 0; break;case 2: dbOff = 0.05; break;case 3: dbOff = 0.10; break;case 4: dbOff = 0.20; break;case 5: dbOff = 0.25; break;}StBuyPlan buyPlan;buyPlan.dbOff = dbOff;for (int j = 0; j < nBuyCount; j++){StBookInfo& bkInfo = vTempList[j];--bkInfo.nBookCount;buyPlan.vBuyBooks.push_back(bkInfo.strVolIdx);}//计算左折扣double dbLeftOff = dbOff*nBuyCount;//计算右折扣,需递归VctBuyPlan vTempPlan;vTempPlan.push_back(buyPlan);double dbRightOff = BuyByDyn(vTempList, vTempPlan);//当前购买方式折扣double dbCurOff = dbLeftOff + dbRightOff;//折扣与组合方式映射mapBuyPlan.insert(make_pair(dbCurOff, vTempPlan));}
}void CDynPrgBuyM::RemoveEmptyBook(VctBookInfo& vBookList)
{VctBookInfo::iterator vIter = vBookList.begin();for (; vIter != vBookList.end();){if (vIter->nBookCount > 0){++vIter;}else{vIter = vBookList.erase(vIter);}}
}CString CDynPrgBuyM::GetBuyKey(const VctBookInfo& vBookList)
{CString strTemp = _T("");CString strKey = _T("");VctBookInfo::const_iterator vIter = vBookList.begin();for (; vIter != vBookList.end(); ++vIter){strTemp.Format(_T("%d"), vIter->nBookCount);strKey += strTemp;strKey += _T("$");}return strKey;
}

运行结果
当前折扣:0.8=0.2*4     购买组合:卷2 卷3 卷4 卷1
当前折扣:0.8=0.2*4     购买组合:卷2 卷3 卷4 卷5
总的折扣:1.6

循环体运行8次即可

  相关解决方案