编程之美-买书问题

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)

{

 //把要买的书的数目按从小到大排序,因为每种书价钱一样,所以一种书放在哪个位置无所谓

 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; //定义一个很大的值,去最小值时不会取到这个值

 

 if(n[0]>0) //数目最少的书都至少有一本,因此此轮可以买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) //数目最少的一种没了,就不能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) //数目最少的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) //数目最少的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) //数目最少的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;

}

最后结果为176