QQ截圖20160317212734.png
QQ截圖20160317212818.png
#include<iostream>
using namespace std;
template <typename T>
void InsertSort(T m[], int length) //插入排序, 從小到大
{
for(int i = 1; i < length; ++i)
{
int j ;
T tmp = m[i];
for( j = i; j>0 && m[j-1]>tmp; --j)
m[j] = m[j-1];
m[j] = tmp;
}
}
double Min(double a, double b, double c, double d, double e) //返回最小值
{
double A[5] = {a, b, c ,d ,e};
InsertSort(A, 5);
return A[0];
}
double BuyBook(int a, int b, int c, int d, int e)
{
//把要買的書的數(shù)目按從小到大排序,因?yàn)槊糠N書價(jià)錢一樣,所以一種書放在哪個(gè)位置無所謂
int n[5] = {a, b, c, d, e};
InsertSort(n, 5);
a = n[0];
b = n[1];
c = n[2];
d = n[3];
e = n[4];
const double large = 100000; //定義一個(gè)很大的值,去最小值時(shí)不會(huì)取到這個(gè)值
if(n[0]>0) //數(shù)目最少的書都至少有一本,因此此輪可以買1, 2, 3, 4, 5,本都行,去最小值,再遞歸
{
return Min(8.0+BuyBook(a, b, c, d, e-1),
2*8.0*0.95 + BuyBook(a, b, c, d-1, e-1),
3*8.0*0.9 + BuyBook(a, b, c-1, d-1, e-1),
4*8.0*0.80 + BuyBook(a, b-1, c-1, d-1, e-1),
5*8.0*0.75 + BuyBook(a-1, b-1, c-1, d-1, e-1));
}
else if(n[0]==0 && n[1]>0) //數(shù)目最少的一種沒了,就不能5種都買了
{
return Min(8.0+BuyBook(a, b, c, d, e-1),
2*8.0*0.95 + BuyBook(a, b, c, d-1, e-1),
3*8.0*0.9 + BuyBook(a, b, c-1, d-1, e-1),
4*8.0*0.80 + BuyBook(a, b-1, c-1, d-1, e-1),
large);
}
else if(n[0]==0 && n[1] == 0 && n[2]>0) //數(shù)目最少的2種沒了,最多買3種
{
return Min(8.0+BuyBook(a, b, c, d, e-1),
2*8.0*0.95 + BuyBook(a, b, c, d-1, e-1),
3*8.0*0.9 + BuyBook(a, b, c-1, d-1, e-1),
large,
large);
}
else if(n[0]==0 && n[1] == 0 && n[2] == 0 && n[3]>0) //數(shù)目最少的3種沒了,最多買2種
{
return Min(8.0+BuyBook(a, b, c, d, e-1),
2*8.0*0.95 + BuyBook(a, b, c, d-1, e-1),
large,
large,
large);
}
else if(n[0]==0 && n[1] == 0 && n[2] == 0 && n[3] == 0 && n[4]>0) //數(shù)目最少的4種沒了,最多買1種
{
return 8.0+BuyBook(a, b, c, d, e-1);
}
else
{
return 0;
}
}
int main()
{
int n[5] = {5,9,3,6,4};
cout<<BuyBook(n[0], n[1], n[2], n[3], n[4])<<endl;
}
最后結(jié)果為176
