背包问题-动态规划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<v){
b[i][j]=b[i-1][j];
continue;
}
b[i][j]=Math.max(b[i-1][j],b[i-1][j-v]+p);
}
}
return b[count][maxVolumen];
}
public static void main(String[] args) {
System.out.println(solution(16,5,volume,price));
}
}
总结
到此这篇关于背包问题-动态规划java实现的文章就介绍到这了,更多相关背包问题 动态规划java实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
java动态规划算法——硬币找零问题实例分析
本文实例讲述了java动态规划算法--硬币找零问题.分享给大家供大家参考,具体如下: 问题描述 现在有3种硬币分别为:1元,5元,10元,现在给你63元,让你全部换成硬币,求出最小硬币数量,也就是说,怎么用最少的硬币数凑成63元. 分析问题 解决这个问题,我们可以将这个大问题分成若干个小问题,自下而上解决问题. 1元对应的最小硬币数是1 2元对应的最小硬币数是2 3元对应的最小硬币数是3 4元对应的最小硬币数是4 -- 63元对应的最小硬币数是XXX 假设我们将前边计算出的金额对应的最小硬币数像
-
Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例
本文实例讲述了Java基于动态规划法实现求最长公共子序列及最长公共子字符串.分享给大家供大家参考,具体如下: 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符
-
Java动态规划之硬币找零问题实现代码
动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,并将这些子问题的解保存起来,如果以后在求解较大子问题的时候需要用到这些子问题的解,就可以直接取出这些已经计算过的解而免去重复运算.保存子问题的解可以使用填表方式,例如保存在数组中. 用一个实际例子来体现动态规划的算法思想--硬币找零问题. 问题描述: 假设有几种硬币,并且数量无限.请找出能够组成某个数目的找零所使用最少的硬币数.例如几种硬币为[1, 3, 5], 面值2的最少硬币数为2(1, 1), 面值4的最少硬币数为2(1,
-
Java矩阵连乘问题(动态规划)算法实例分析
本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确
-
Java动态规划之编辑距离问题示例代码
动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,
-
Java面试之动态规划与组合数
最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我们一起来回顾一下. 从题目说起 题目原文是: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为"Start" ). 机器人每次只能向下或者向右移动一步.机器人试图达到网格的右下角(在下图中标记为"Finish"). 问总共有多少条不同的路径? 例如,上图是一个7 x 3 的网格.有多少可能
-
背包问题-动态规划java实现的分析与代码
一.动态规划的原理 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划.1957年
-
Java CPU性能分析工具代码实例
这篇文章主要介绍了Java CPU性能分析工具代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 背景 有处理过生产问题的同学基本都能遇到系统忽然缓慢,CPU突然飙升,甚至整个应用请求不可用.当出现这种情况下,在不影响数据准确性的前提下,我们应该尽快导出jstack和内存信息,然后重启系统,尽快回复系统的可用性,避免用户体验过差.本文针对CPU飙升问题,提供该问题的排查思路,从而能够快速定位到某线程甚至某快代码导致CPU飙升,从而提供处理该
-
Java语言求解完美数代码分析
1.概念 首先我们理解一下,什么叫做完美数? 问题描述:若一个自然数,它所有的真因子(即除了自身以外的约数)的和恰好等于它本身,这种数叫做完全数.简称"完数" 例如, 6=1+2+3 28=1+2+4+7+14 496=1+2+4+8+16+31+62+124+248 8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064 按照完数的定义,其实用程序求解完数并不是太难,先求解出这个数的所有真因子,然后相加,判断是否等于它本身即可.但是,在这个数
-
java语言求解兔子问题代码分析
1.思考 兔子问题,是费氏数列的形象化说法,它是由一位名为Fibonacci的数学家在它的著作中提出的一个问题. 2.描述 它体术的问题是:若有一只免子每个月生一只小免子,一个月后小免子也开始生产.起初只有一只免子,一个月后就有两只免子,二个月后有三只免子,三个月后有五只免子(小免子投入生产)...... 我们使用数学的方式表达出来,便是下面的一组数列: 1.1.2.3.5.8.13.21.34.55.89...... 注意:新生的小免子需一个月成长期才会投入生产!而且这些兔子是不死的哦!!!
-
Java动态代理分析及理解
Java动态代理分析及理解 代理设计模式 定义:为其他对象提供一种代理以控制对这个对象的访问. 动态代理使用 java动态代理机制以巧妙的方式实现了代理模式的设计理念. 代理模式示例代码 public interface Subject { public void doSomething(); } public class RealSubject implements Subject { public void doSomething() { System.out.println( "call
-
Java 冒泡排序、快速排序实例代码
冒泡排序 冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地 进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序的算法实现如下:[排序后,数组从小到大排列] /** * 冒泡排序 * 比较相邻的元素.如果第一个比第二个大,就交换他们两个. * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应
-
Android系统进程间通信Binder机制在应用程序框架层的Java接口源代码分析
在前面几篇文章中,我们详细介绍了Android系统进程间通信机制Binder的原理,并且深入分析了系统提供的Binder运行库和驱动程序的源代码.细心的读者会发现,这几篇文章分析的Binder接口都是基于C/C++语言来实现的,但是我们在编写应用程序都是基于Java语言的,那么,我们如何使用Java语言来使用系统的Binder机制来进行进程间通信呢?这就是本文要介绍的Android系统应用程序框架层的用Java语言来实现的Binder接口了. 熟悉Android系统的读者,应该能想到应用程序框架
-
浅谈Java多线程的优点及代码示例
尽管面临很多挑战,多线程有一些优点使得它一直被使用.这些优点是: 资源利用率更好 程序设计在某些情况下更简单 程序响应更快 资源利用率更好 想象一下,一个应用程序需要从本地文件系统中读取和处理文件的情景.比方说,从磁盘读取一个文件需要5秒,处理一个文件需要2秒.处理两个文件则需要: 5秒读取文件A 2秒处理文件A 5秒读取文件B 2秒处理文件B --------------------- 总共需要14秒 从磁盘中读取文件的时候,大部分的CPU时间用于等待磁盘去读取数据.在这段时间里,CPU非常的
-
java 导入Excel思路及代码示例
导出就是将List转化为Excel(listToExcel) 导入就是将Excel转化为List(excelToList) 一.思路分析 1.我们要做导入,实际上也就是先文件上传,然后读取文件的数据. 2.我们要有一个导入的模板,因为我们导入的Excel列要和我们的数据字段匹配上,所以我们要给它来一个规定,也就是模板. 3.按照我们公司的套路,是做了一个导入信息的临时表,用来存导入文件中的信息.每当导入的时候,我们先把表信息清空,再拿到数据放进来,然后我们对导入的数据进行检查,最后才全部导入.
-
java中switch选择语句代码详解
switch结构(开关语句)的语法 switch(表达式 ){ --->类型为int.char case 常量1 :--->case 结构可以有多个 //语句块1 break; --->程序跳出switch结构 case 常量n :--->常量的值不能相同 //语句块n break; default:--->和if结构中的 else作用相同 //语句块 break; } 下面看一段代码示例,有详细的注释,大家可以参考: public class SwitchStu{ /* s