这个问题来自《编程之美》这本书,应该在微软面试中出现过。是一个典型的动态规划问题。
问题描述
《哈利波特》系列一共有五卷,每一卷售价均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次即可