废话：
最近刚买了本书《编程之美》，首先看了下时间：2008.3。刚好是大二的时候，真希望回到那时，买一本《编程之美》，坐在宿舍，吃着热干面，编着代码。刹那间，有种相见恨晚的感觉，前一阵，也感觉自己浮夸的很，什么流行就看什么。是时候按下心来，好好享受下beauty of programming
本文来自：http://blog.csdn.net/lengzijian/article/details/7789222
问题：
某书店对《哈利波特》做促销活动，一共有5卷。假设每一卷的单独销售价格为8元，如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多，优惠如下：
本数
折扣
2
5%
3
10%
4
20%
5
25%
求出购买一批书的最低价格？
刚拿过题目第一感觉就是用贪心方法，不出所料书中最开始提到的就是贪心规则。首先看下10本数以内的折扣表：
本数
所有组合
折扣
节省的钱
2-5
2
3
4
5
0.1
0.3
0.8
1.25
0.8
2.4
6.4
10
6
5+1
4+2
3+3
2+2+2
1.25
0.9
0.6
0.3
10
7.2
4.8
2.4
7
5+2
4+3
3+2+2
1.35
1.1
0.5
10.8
8.8
4
8
5+3
4+4
3+3+2
2+2+2+2
1.55
1.6
0.7
0.4
12.4
12.8
5.6
3.2
9
5+4
5+2+2
4+3+2
3+3+3
2.05
1.45
1.2
0.9
16.4
11.6
9.6
7.2
10
5+5
4+4+2
4+3+3
2+2+2+2+2
2.5
1.7
1.4
0.5
20
13.5
11.2
4
这里不再讲解贪心算法，我想记录下动态规划法几个比较难理解的地方。
注：书中用的是最少花费，而我用的是最多节省钱数。之后可以通过表达式看出区别。
1. 在书中，假设用Xn表示购买第n卷数的数量，那么购买所有书数量可以用(X1,X2,X3,X4,X5)表示，而F(X1,X2,X3,X4,X5)表示最多节省钱数。为了使书籍没有编号顺序，即(X1,X2,X3,X4,X5)和(X3,X2,X1,X4,X5)为一样的变量，书中使用的“最小表示”。Y1,Y2,Y3,Y4,Y5是X1,X2,X3,X4,X5的重新排列，满足Y1>=Y2>=Y3>=Y4>=Y5。在之后的所有阐述中，购买数的数量均以“最大满足”方法，放入变量。例如:
我要买8本书，那么变量的存储值为(2,2,2,1,1);
如果我要买10本书，那么变量存储值为(2,2,2,2,2)，为何不是(5,5,0,0,0)
以一种循环+1，最大满足所有变量的方式赋值，为什么如此？
个人拙见：
以10本书为例，当用(5,5,0,0,0)为变量时，会有5种(1+2)的方法(1+2：表示第一卷加上第二卷的组合方式)，而同样，当用(2,2,2,2,2)为变量时，可以有([1+2] ,[2+3] ,[3+4] ,[4+5] ,[5+1])共5种两两组合，即所有的组合方式都是“做大满足”方法的子集，都可以用“做大满足”方法模拟其他变量存储方式。
2. 假定要买的书为(Y1,Y2,Y3,Y4,Y5),如果第一次考虑为5本不同卷付钱(Y5>=1)，那么剩下数的集合为(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1);但是如果要为4本不同卷付钱，剩下几何应该有如下种：
(Y1-1,Y2-1,Y3-1,Y4-1,Y5);
(Y1-1,Y2-1,Y3-1,Y4,Y5-1);
(Y1-1,Y2-1,Y3,Y4-1,Y5-1);
(Y1-1,Y2,Y3-1,Y4-1,Y5-1);
(Y1,Y2-1,Y3-1,Y4-1,Y5-1);
我们该如何选择然后继续分析下去呢？
举例说明：
假设Y1=Y2=Y3=Y4=Y5=2.
选择(1,1,1,1,0),剩下(Y1-1,Y2-1,Y3-1,Y4-1,Y5)的组合为(1,1,1,1,2)，剩下的书为{1,2,3,4,5,5};
选择(1,1,1,0,1),剩下(Y1-1,Y2-1,Y3-1,Y4,Y5-1)的组合为(1,1,1,2,1)，剩下的书为{1,2,3,4,4,5};
由于Y4>=Y5>Y5-1，后者方案中，总会有一种方案里只有4卷而没有5卷，完全可以把只有4没有5的组合，换成5卷。例如：
{1,2,3,4}{4,5}->{1,2,3,5}{4,5}
对于任何(Y1-1,Y2-1,Y3-1,Y4,Y5-1)的最优解，都能转化为(Y1-1,Y2-1,Y3-1,Y4-1,Y5)的解。
有了上面两个依据，就可以写出推导公式：
因为我求的是最大节约钱数，所以跟书上有一点不同
F(Y1,Y2,Y3,Y4,Y5)
if(Y1=Y2=Y3=Y4=Y5=0)
return 0;
return max(
5*8*25% + F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1) (Y5 >=1),
4*8*20% + F(Y1-1,Y2-1,Y3-1,Y4-1,Y5) (Y4>=1),
3*8*10% + F(Y1-1,Y2-1,Y3-1,Y4,Y5) (Y3 >=1),
2*8*5% + F(Y1-1,Y2-1,Y3,Y4,Y5) (Y2 >=1),
1*8*0% + F(Y1-1,Y2,Y3,Y4,Y5) (Y1 >=1)
)
记得要转化成对应的最小表示(书上很清楚，这里就不赘述了)：
F(1,2,2,2,2)----------转化-----------> F(2,2,2,2,1)
下面是我实现的c语言版本：
#include<stdio.h>
//折扣信息(逆序)
//个人不喜欢float，所以在结果后除以100就可以了
int change[5] = {25,20,10,5,0};
//求数组中最大的值
//用于取出做大节约钱数
int max_index(int a[5]){
int max=0;
int i;
for(i=0;i<5;i++){
if(max < a[i])
max = a[i];
}
return max;
}
//冒泡排序
//用于转化最小表示(1,2,2,2,2)->(2,2,2,2,1)
void bubble(int *a,int n)
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i]<a[j]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
//递归函数
int func(int a[5]){
int i,j,k;
int buf[5];
int cash[5];
for(i=0;i<5;i++){
cash[i] = 0;
//buf[i] = a[i];
}
//退出条件
if(a[0]==a[1]&&a[1]==a[2]&&a[2]==a[3]&&a[3]==a[4]&&a[4] == 0){
return 0;
}
//排序 转化最小表示
bubble(a,5);
//5次循环
for(i=1;i<=5;i++){
if(a[5-i] >= 1){
for(k=0;k<5;k++){
buf[k] = a[k];
}
//减一
for(j=0;j<=5-i;j++)
buf[j] = buf[j]-1;
//继续递归
cash[i-1] = (5-i+1)*8*change[i-1]+func(buf);
}
}
//返回最大值
return max_index(cash);
}
int main(){
//a数组用于表示所选的方案2,2,2,2,2表示选10本书
//这里之前讲过，为什么要这么做了。。
//读者也可以自己写“最大满足”的函数
int a[5] = {2,2,2,2,2};
float result =0;
result = func(a);
printf("result %2.2f\n",result/100);
}
|
查看运行结果：
当为10本书时：int a[5] = {2,2,2,2,2};
result 20.00
当为8本书时：int a[5] = {2,2,2,1,1};
result 12.80
与之前表里里面的数据一模一样，安心了(话说，调试递归什么的最讨厌了)。