买书问题dp实现题目:买书有一书店引进了一套书,共有3卷,每卷书定价是60元,书店为了搞促销,推出一个活动,活动如下:如果单独购买其中一卷,那么可以打9.5折。
如果同时购买两卷不同的,那么可以打9折。
如果同时购买三卷不同的,那么可以打8.5折。
如果小明希望购买第1卷x本,第2卷y本,第3卷z本,那么至少需要多少钱呢?(x、y、z为三个已知整数)。
1、过程为一次一次的购买,每一次购买也许只买一本(这有三种方案),或者买两本(这也有三种方案),或者三本一起买(这有一种方案),最后直到买完所有需要的书。
2、最后一步我必然会在7种购买方案中选择一种,因此我要在7种购买方案中选择一个最佳情况。
3、子问题是,我选择了某个方案后,如何使得购买剩余的书能用最少的钱?并且这个选择不会使得剩余的书为负数。
母问题和子问题都是给定三卷书的购买量,求最少需要用的钱,所以有"子问题重叠",问题中三个购买量设置为参数,分别为i、j、k。
4、的确符合。
5、边界是一次购买就可以买完所有的书,处理方式请读者自己考虑。
6、每次选择最多有7种方案,并且不会同时实施其中多种,因此方案的选择互不影响,所以有"子问题独立"。
7、我可以用minMoney[i][j][k]来保存购买第1卷i本,第2卷j本,第3卷k本时所需的最少金钱。
8、共有x*y*z个问题,每个问题面对7种选择,时间为:O(x*y*z*7)=O(x*y*z)。
9、用函数MinMoney(i,j,k)来表示购买第1卷i本,第2卷j本,第3卷k本时所需的最少金钱,那么有:MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分别为对应的7种方案使用的最少金钱:s1=60*0.95+MinMoney(i-1,j,k)s2=60*0.95+MinMoney(i,j-1,k)s3=60*0.95+MinMoney(i,j,k-1)s4=(60+60)*0.9+MinMoney(i-1,j-1,k)s5=(60+60)*0.9+MinMoney(i-1,j,k-1)s6=(60+60)*0.9+MinMoney(i-1,j,k-1)s7=(60+60+60)*0.85+MinMoney(i-1,j-1,k-1)
1