- 浏览: 52794 次
文章分类
最新评论
背包的算法的动态方式如下:
状态转移方程理解如下:
f(i,w)表示前i个物体面对容量为w时背包的最大价值,weight[i]代表物体i的重量(即重量),value[i]代表物体i的价值;如果第i个物体不放入背包,则背包的最大价值等于前i-1个物体面对容量v的最大价值;如果第i个物体选择放入,则背包的最大价值等于前i-1个物体对容量w-weight [i]的最大价值加上物体i的价值value[i]。
综上,第i件物品要么选,要么不选。
1)如果不选,则第i件物品放w容量的最优值等于第i-1件物品放w容量的最优值;
2)如果i选,则第i件物品放w-weight容量的最优值再加value[i]的值。
现在我们的问题是:在一个数组中有若个数据,找出最接近所有数据10%的值?而且我们的实际情况是数组中存在的是实数,物品只有三百个左右,而待查找的数是几十万的情况。
做法:
1)所有的数据进行格式化处理,剔除小于100的数,实数四舍五入变正整数;
2)待查找的数降100倍,同时格式化的数据也进行降100倍处理,这样可以大大节省内存空间。
核心代码如下:
f(i,w) = max{ f(i-1,w), f(i-1,v-weight[i])+value[i] }
状态转移方程理解如下:
f(i,w)表示前i个物体面对容量为w时背包的最大价值,weight[i]代表物体i的重量(即重量),value[i]代表物体i的价值;如果第i个物体不放入背包,则背包的最大价值等于前i-1个物体面对容量v的最大价值;如果第i个物体选择放入,则背包的最大价值等于前i-1个物体对容量w-weight [i]的最大价值加上物体i的价值value[i]。
综上,第i件物品要么选,要么不选。
1)如果不选,则第i件物品放w容量的最优值等于第i-1件物品放w容量的最优值;
2)如果i选,则第i件物品放w-weight容量的最优值再加value[i]的值。
现在我们的问题是:在一个数组中有若个数据,找出最接近所有数据10%的值?而且我们的实际情况是数组中存在的是实数,物品只有三百个左右,而待查找的数是几十万的情况。
做法:
1)所有的数据进行格式化处理,剔除小于100的数,实数四舍五入变正整数;
2)待查找的数降100倍,同时格式化的数据也进行降100倍处理,这样可以大大节省内存空间。
核心代码如下:
public static void beiBao() { // 背包的容量大小,最大的数据为50w,10%就是5w,再降100倍,即为500 int dp[] = new int[501]; char state[][] = new char[deal_Array.length][501]; /* 记录路径的二维数组 */ int i, j; int M = 49602 / 100; // 待查找近似值 /* 01背包 */ for (i = 0; i < deal_Array.length; ++i) { for (j = M; j >= deal_Array[i]; --j) { int tmp = dp[j - deal_Array[i]] + deal_Array[i]; if (tmp > dp[j]) { dp[j] = tmp; state[i][j] = 1; } } } i = deal_Array.length; // 第几个商品 j = M;// 当前背包容量 System.out.println("============================"); while ((--i) >= 0) { if (state[i][j] == 1) { System.out.print(deal_Array[i] + " "); j -= deal_Array[i]; } } }
发表评论
-
Java IO 读文件的各种方法总结
2016-01-01 15:00 693IO分为字节流和字符流,字符就是简单的字符串存储,从理伦上讲, ... -
动态代理的应用
2015-12-22 17:30 731代理模式作为开发人员 ... -
Java Restful
2015-12-19 14:01 437对于两个系统之间交互信息,有两种常见的方式:webservic ... -
request.getInputStream() 只能读一次的解决方法
2015-12-17 12:17 2376我们知道request.getInputStream()只能读 ... -
java Hessian 版本冲突问题解决方法
2015-12-11 19:44 861今天在实际的项目发现了一个问题就是hessian的版本不兼容的 ... -
ThreadPoolExecutor参数讲解
2015-12-10 08:14 8141. 线程池可以节省创建多个线程带来的开销问题。 2. 线程 ... -
Java RSA 加密 解密 签名 验签
2015-12-09 10:01 61441. 加密的作用 1)明文变密文(你不知道密钥是很难解密的) ... -
Java Xstream xml 与bean之间的转换
2015-12-09 08:31 744xml文件如下: <mvc> & ... -
XPATH 解析XML
2015-12-09 08:28 4321. 表达式描述 nodename 选取此节点的所有子节 ... -
Java Dom4j 解析XML
2015-12-09 08:23 363Dom4j和JDom是很相似的,用起来十分方便。 XML文件 ... -
Java JDom 解析xml
2015-12-09 08:22 414JDOM在解析XML在代码量之上比之前的方法(DOM和SAX要 ... -
Java SAX 解析xml
2015-12-08 18:13 417在上一篇中http://gaofulai1988.iteye. ... -
Java XML解析系列
2015-12-08 18:00 749Java解析XML有多种方式,因此需要分为几个不同的系列来讲。 ... -
C3P0 连接分析
2015-12-01 19:05 888最近在看C3P0的原理,还是将C3P0的源码导入到Ecplis ... -
微信开发的原理
2015-11-30 10:10 1314微信在现在的生活中,扮演着举足轻重的角色,现在怎么东西都在微信 ... -
JAVA Timestamp 与Data的转化以及BigDecimal 保留两位小数
2015-11-27 14:47 16951. BigDecimal 保留两位小数 今天在项目中遇到这 ... -
java try catch finally return 继续
2015-11-27 13:45 400之前在博客中有一篇文章讨论过异常中return值的情况,有兴趣 ... -
Java JDBC executeBatch 批量操作
2015-11-27 08:05 1627对JDBC 的 CRUD操作,我相信对于每个开发人员来讲,是十 ... -
Java WeakHashMap 分析
2015-11-26 08:17 619昨天在我们的系统中看 ... -
加密与解密
2015-11-18 18:12 479我本身不是学密码出身的,但在工作中经常要使用加密与解密的东东, ...
相关推荐
目标是从这`n`个物品中选择若干个放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。 #### 二、回溯算法原理 回溯算法是一种通过试探搜索解决问题的方法,它尝试构建问题的所有解,并逐步检查这些...
为此,我们定义一个二维数组,其中每个元素代表一个状态,即前个物体中若干个放入体积为背包中最大价值。数组为:,其中表示前件中若干个物品放入体积为的背包中的最大价值。 ②、初始状态 初始状态为和都为...
7. **分治算法**:分治策略将大问题分解为若干个相同或相似的小问题,然后逐个解决。如快速排序、归并排序和大整数乘法等。 8. **数据结构**:Java中的数据结构如数组、链表、栈、队列、树(二叉树、平衡树如AVL、...
10. **分治算法**:将大问题划分为若干个相似的小问题,分别解决后再合并,如快速排序、归并排序、大整数乘法等。 通过学习这个Java算法大全,不仅可以掌握各种算法的实现,还能深入理解其背后的逻辑和思想,这对于...
Java面试中的算法问题通常涉及到数据结构、排序、搜索、图论等多个方面,是评估候选人编程能力和逻辑思维的重要标准。在准备Java面试时,理解和熟练掌握这些算法至关重要,因为它们不仅体现了程序员的基础技能,还能...
0/1背包问题是指给定一组物品,每种物品都有自己的重量和价值,在限定的总重量内,选择其中若干个(也可以是0个),设计选择方案使得总价值最高。 在代码片段中,定义了一个Fruit类,用于表示每种物品,包含名称、...
在Java编程语言中,算法通常指的是高效地处理数据和执行计算的方法。Java提供了丰富的库和工具来支持各种算法的实现,使得开发者能够用Java解决复杂的问题。 在Java中,算法的应用非常广泛,包括排序、搜索、图论、...
在编程领域,尤其是Java开发中,数据结构和算法是核心基础,它们对于编写高效、可扩展的代码至关重要。本文将深入探讨Java中的数据结构和算法,帮助你提升编程能力。 一、数据结构 数据结构是组织和管理数据的方式...
动态规划是一种解决多阶段决策过程中的最优化问题的方法,其基本思想是将原问题分解为若干个相互重叠的子问题,并保存子问题的解避免重复计算。 **2. 动态规划的基本要素** - **最优子结构**: 问题的最优解包含了其...
"JAVA经典算法"这个压缩包文件很可能是汇集了一些在实际开发中常见的、高效的算法实现,对于学习和提升编程技能非常有帮助。以下是对这些算法的详细介绍: 1. **排序算法**:包括快速排序、归并排序、冒泡排序、...
2. 分治:分治策略将大问题分解为若干个相同或相似的小问题,分别解决,再合并结果。快速排序、归并排序都是典型的分治算法。 五、动态规划 动态规划是一种通过构建子问题的最优解来解决原问题的算法,常用于背包...
dp[i][j]的值代表前i个物品中选择若干个(总重量不超过j)的最大价值。初始化时,当没有物品时,背包的最大价值为0,即dp[0][j] = 0。然后,对每个物品,我们有两种选择:包含它或者不包含它。如果包含第i个物品且其...
Java数据结构和算法实现是一个深度探讨编程基础的重要主题,它涉及到如何高效地组织和操作数据。数据结构是存储和组织数据的方式,而算法是解决问题或执行任务的特定步骤。在这个zip文件中,"ljg_resource1"可能是一...
1. 线性查找:线性查找是最简单的查找算法,从数组的一端开始,逐个与目标值比较,直到找到目标值或者搜索完整个数组。 2. 二分查找:二分查找也称为折半查找,适用于已排序的数组。它通过不断将查找区间缩小一半来...
Java算法是计算机科学中的核心部分,它涉及到一系列用于解决复杂问题的方法和技术,这些方法和技术在Java编程中扮演着至关重要的角色。Java作为一种广泛使用的面向对象的编程语言,提供了丰富的库和工具来支持算法的...
这是因为我们需要尝试所有n个物品的2^n种可能的选中状态,并且对每种状态检查其是否符合背包的容量限制,计算其总价值。 蛮力法的C#实现步骤如下: 1. 定义物品类:每个物品都有一个重量(weight)和一个价值...
**实现**:示例代码首先初始化了一个二维数组`m`用于存储子问题的解,其中`m[i][j]`表示前`i`件物品在容量为`j`的背包中的最大价值。然后通过两层循环更新这个数组,最终得到的最大值即为所求。 **特点**:能够有效...
在IT行业中,动态规划是一种非常重要的算法,广泛应用于各种复杂问题的求解,如最短路径、背包问题、任务调度等。在这个特定的压缩包文件中,我们关注的是水库调度程序,它涉及到如何有效地管理水库的水资源,以满足...
- 在线性时间内找到未排序数组中的中位数或其他序统计量。 **3.10 最接近点对问题** - 寻找一组点中距离最近的两点。 **3.11 循环赛日程表** - 设计合理的比赛日程安排。 #### 四、动态规划 动态规划是一种用于...