import java.util.Arrays;
public class BookDiscount {
/**编程之美 买书折扣
书上的贪心算法的分析很有意思,我看了半天看不懂,结果作者说,贪心算法在这个问题上是不适用的。。
下面用动态规划实现。
哈利波特这本书一共有五卷,每卷都是8欧元,如果读者一次购买不同的两卷可扣除5%的折扣,三卷10%,四卷20%,五卷25%。现在我要买很多本书,应该怎么组合才最省钱?
我们用F(Y1,Y2,Y3,Y4,Y5)表示这五卷书分别Yi本时的最少花销。
由于购买(2本卷一其余只购1本)和购买(2本卷二其余只购1本)(因为每卷书的价格是一样的,因此书的顺序是无所谓的)的最少花销是一样的,即F(2,1,1,1,1)=F(1,2,1,1,1)=F(1,1,2,1,1)=......。
我们用F(2,1,1,1,1)来代表这一组方案的“最小表示”,即在一个最小表示F(Y1,Y2,Y3,Y4,Y5)中满足Y1>=Y2>=Y3>=Y4>=Y5。
用动态规划我们可以建立状态转移方程:
F(Y1,Y2,Y3,Y4,Y5)
=0 if(Y1=Y2=Y3=Y4=Y5=0)
=min{
40*0.75+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1) , if(Y5>=1)
32*0.8+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5) , if(Y4>=1)
24*0.9+F(Y1-1,Y2-1,Y3-1,Y4,Y5) , if(Y3>=1)
16*0.95+F(Y1-1,Y2-1,Y3,Y4,Y5) , if(Y2>=1)
8+F(Y1-1,Y2,Y3,Y4,Y5) , if(Y1>=1)
}
状态转移之后得到的F(Y1-1,Y2-1,Y3-1,Y4-1,Y5)等可能不是“最小表示”,要把它转化为对应的“最小表示”。
*/
public static void main(String[] args) {
BookDiscount bookDiscount=new BookDiscount();
int[][] books={
{2,2,2,1,1},
{4,3,2,1,0}
};
for(int[] each:books){
double min=bookDiscount.findMinCost(each[0],each[1],each[2],each[3],each[4]);
System.out.println(Arrays.toString(each)+",min cost="+min);
}
}
public double findMinCost(int Y1,int Y2,int Y3,int Y4,int Y5){
int[] x={Y1,Y2,Y3,Y4,Y5};
Arrays.sort(x);
if(x[0]<0){
System.out.println("购书数量不能为负数");
return 0;
}
//Y1>=Y2>=Y3>=Y4>=Y5
Y5=x[0];
Y4=x[1];
Y3=x[2];
Y2=x[3];
Y1=x[4];
double cost=0;
if(Y5>=1){
cost=min(
8*5*(1-0.25)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1),
8*4*(1-0.20)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5),
8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),
8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)
);
}else if(Y4>=1){
cost=min(
8*4*(1-0.20)+findMinCost(Y1-1,Y2-1,Y3-1,Y4-1,Y5),
8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),
8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)
);
}else if(Y3>=1){
cost=min(
8*3*(1-0.10)+findMinCost(Y1-1,Y2-1,Y3-1,Y4,Y5),
8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)
);
}else if(Y2>=1){
cost=min(
8*2*(1-0.05)+findMinCost(Y1-1,Y2-1,Y3,Y4,Y5)
);
}else if(Y1>=1){//{Y1,0,0,0,0},说明买的是同一卷书,没有折扣
cost=8*Y1;
}else{//{0,0,0,0,0}
cost=0;
}
return cost;
}
public double min(double y,double...yy){
double m=y;
for(double e:yy){
if(m>e){
m=e;
}
}
return m;
}
}
分享到:
相关推荐
●编程语言:C# ●数据库:SQL SERVER 二、需求分析 网上书店系统为用户提供一系列网上购书服务。 系统包含两类用户,即管理员和普通用户。针对这两类用户,系统根据登录时的角色判断,跳转到相应的页面为其提供操作...
布拉格编程网 优惠券turkeysale2020可节省 40% 11/23 Apress.com 6.99 美元电子书,带代码CYBER20AP 11/25 HPB.com 使用代码FRIDAY20 20% 的折扣 11/25 图书 网站 细节 作为 关联 网络管道工手册、实验室指南和交互...
学习小组 我们的研究小组将基于《 (又名红皮书)一书。 我们相信,这本书将实现我们的目标:理解和应用函数式编程。 正如我们在第一次见面会中已经提到的那样,这本书基于Scala语法,这并不意味着它的目的就是学习...
详细设计说明书 文档标识: 当前版本: 1.0 当前状态: 草稿 发布日期: 2012-8-28 发布 修改历史 日期 版本 作者 修改内容 评审号 变更控制号 2012-8-28 1.0 拓维 新建 ...
amazon有折扣 http://www.amazon.com/Pro-2010-NET-Platform-Fifth/dp/1430225491/ref=sr_1_1?ie=UTF8&s=books&qid=1261446530&sr=8-1 C#与.NET3.5高级程序设计(第4版) 中文 其他网友本资源我下了,都没有下载下来...
amazon有折扣 http://www.amazon.com/Pro-2010-NET-Platform-Fifth/dp/1430225491/ref=sr_1_1?ie=UTF8&s=books&qid=1261446530&sr=8-1 C#与.NET3.5高级程序设计(第4版) 中文 其他网友本资源我下了,都没有下载下来...
本书尤其适合作为你的引路书籍,因为它翔实地介绍了初学者入门时所必需的知识积累,而这些知识在《操作系统:设计与实现》一书中是没有涉及的,笔者本人是把这本书作为写操作系统的主要参考书籍之一,所以在本书中对...
本书尤其适合作为你的引路书籍,因为它翔实地介绍了初学者入门时所必需的知识积累,而这些知识在《操作系统:设计与实现》一书中是没有涉及的,笔者本人是把这本书作为写操作系统的主要参考书籍之一,所以在本书中对...
净现值:假设年折扣率为10%则:第一年收益为13500;第二年为38000, 折算为38000*0.9091=34545.8;第三年收益为60000,折算为 60000*0.8264=49584。所以总收益为97629.8,净收益为36629.8。 7社会因素方面的可行性 ...
不需要专门编程,半天便能建立门户级专业电子商务购物网站。购物系统轻松管理维护,经济效率实实在在看得见。如不会本机调试本系统,请查看《IIS安装使用说明书》 电子商务购物网站管理系统前台功能栏目 本系统包含...
HybridApp 一种可以下载的Native App,其用户界面的全部或者部分元素在嵌入式浏览器组件(WebView之类的)里面运行 优雅降级 一开始就构建站点的完整功能,然后针对浏览器测试和修复。认为应该针对那些最高级、最...