这期内容当中小编将会给大家带来有关利用java怎么实现一个动态规划功能,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
创新互联建站是一家集网站建设,梁平企业网站建设,梁平品牌网站建设,网站定制,梁平网站建设报价,网络营销,网络优化,梁平网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;
1、分析
题目:在某个深夜里,一个小偷背着一个总共只能装16v体积的背包进入一家商店偷东西。假如店里有手机一部,价格为2000元,体积为1v;薯片一包,价格为5元,体积为5v;翡翠一块,价格为100000元,体积为10v;一套四大名著,价格30元,体积为6v;电脑一台,价格为6000元,体积为10v。怎么样能够让背包装的下,并且又能使拿到的东西总价格最多?
这种情况下,一共5件东西。小偷偷东西的事件只有两种:拿,不拿。
当他拿的时候,背包体积变小,物件数量减1;当他不拿的时候,背包体积不变,物件数量减1(因为小偷选择不拿这件东西的时候不会返回继续拿,所以他失去了这件东西选择的机会)。
物件数量为i,背包容纳量为v。
1.不拿 b(i-1,v)
2.拿 b(i-1,v-该物品的体积)
两者取较大值
核心代码:
b[i][j]=Math.max(b[i-1][j],b[i-1][j-v]+p);
2、代码分析
public class _背包问题 { //物品体积 private static int[] volume={1,5,10,6,10}; //物品价格 private static int[] price={2000,5,100000,30,6000}; //背包容量 private static int maxVolumen=16; //物品数量 private static int count=5; public static int solution(int maxVolumen,int count,int[] volume,int[] price){ int[][] b=new int[count+1][maxVolumen+1]; for (int i=1;i<=count;i++){ //拿到物品的价格 int p=price[i-1]; //拿到物品的体积 int v=volume[i-1]; for (int j=1;j<=maxVolumen;j++){ //如果物品的体积大于背包容量时,选择不拿。 if (j上述就是小编为大家分享的利用java怎么实现一个动态规划功能了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。
标题名称:利用java怎么实现一个动态规划功能-创新互联
标题URL:http://njwzjz.com/article/dcphio.html