- 浏览: 49770 次
文章分类
最新评论
背包的算法的动态方式如下:
状态转移方程理解如下:
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 663IO分为字节流和字符流,字符就是简单的字符串存储,从理伦上讲, ... -
动态代理的应用
2015-12-22 17:30 690代理模式作为开发人员 ... -
Java Restful
2015-12-19 14:01 395对于两个系统之间交互信息,有两种常见的方式:webservic ... -
request.getInputStream() 只能读一次的解决方法
2015-12-17 12:17 2290我们知道request.getInputStream()只能读 ... -
java Hessian 版本冲突问题解决方法
2015-12-11 19:44 818今天在实际的项目发现了一个问题就是hessian的版本不兼容的 ... -
ThreadPoolExecutor参数讲解
2015-12-10 08:14 7751. 线程池可以节省创建多个线程带来的开销问题。 2. 线程 ... -
Java RSA 加密 解密 签名 验签
2015-12-09 10:01 58651. 加密的作用 1)明文变密文(你不知道密钥是很难解密的) ... -
Java Xstream xml 与bean之间的转换
2015-12-09 08:31 692xml文件如下: <mvc> & ... -
XPATH 解析XML
2015-12-09 08:28 3971. 表达式描述 nodename 选取此节点的所有子节 ... -
Java Dom4j 解析XML
2015-12-09 08:23 326Dom4j和JDom是很相似的,用起来十分方便。 XML文件 ... -
Java JDom 解析xml
2015-12-09 08:22 359JDOM在解析XML在代码量之上比之前的方法(DOM和SAX要 ... -
Java SAX 解析xml
2015-12-08 18:13 360在上一篇中http://gaofulai1988.iteye. ... -
Java XML解析系列
2015-12-08 18:00 678Java解析XML有多种方式,因此需要分为几个不同的系列来讲。 ... -
C3P0 连接分析
2015-12-01 19:05 850最近在看C3P0的原理,还是将C3P0的源码导入到Ecplis ... -
微信开发的原理
2015-11-30 10:10 1275微信在现在的生活中,扮演着举足轻重的角色,现在怎么东西都在微信 ... -
JAVA Timestamp 与Data的转化以及BigDecimal 保留两位小数
2015-11-27 14:47 15941. BigDecimal 保留两位小数 今天在项目中遇到这 ... -
java try catch finally return 继续
2015-11-27 13:45 361之前在博客中有一篇文章讨论过异常中return值的情况,有兴趣 ... -
Java JDBC executeBatch 批量操作
2015-11-27 08:05 1545对JDBC 的 CRUD操作,我相信对于每个开发人员来讲,是十 ... -
Java WeakHashMap 分析
2015-11-26 08:17 577昨天在我们的系统中看 ... -
加密与解密
2015-11-18 18:12 438我本身不是学密码出身的,但在工作中经常要使用加密与解密的东东, ...
相关推荐
原先在网上找到某位大虾写的一个简单的背包算法,于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合(其中的对象中只包含主键和值)和某个条件值,然后能打印sum(对象.值)条件的1个...
背包算法 背包算法JAVA实现 背包算法JAVA实现
背包算法规划求解,解决问题场景如:售货架中有n种商品(每种商品只有一个),给定200块钱购物,尽可能的购买到更多的商品,将这本金最大化利用。
用贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。
一个找游戏中背包数组的教程,用CE和OD配合寻找
java 0-1背包算法
这个是背包算法。。解决背包问题的java代码。。。。。。。。。。。。。。。。。。。。。。
用遗传算法解决多维背包问题,采用java代码。用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码。
用贪心算法实现背包问题 集SSH框架,android,行业资讯,数据库,web开发,设计模式希望大家一起分享
背包 背包问题 背包算法 背包 noip 竞赛 信息技术 基础算法
java编写的,完全背包算法,含完整注释。包裹包含重量和体积两个维度。
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
先前发布的背包算法在实际应用中效果不佳,数据量大了就出stackoverflow的问题,于是索性重写了。源码共产给大家,望大家多多指点,谢谢大家!
探究-贪心算法解决背包问题(Java实现)
用回溯算法解决背包问题,和我上传的另一个资源一样的只不过哪个用贪心算法解决,大家可以下来对比学习,用netbeans做的。百分百下载就可以直接运行。有WORD文档实验报告,和 JAVA 源文件。
0/1背包问题动态规划算法 一维数组实现 测试结果: 0 4 5 9 10 11 15 15 17 18 19 23 23 包负重为12时最优结果值为:23 包负重为1时最优结果物品组成:[w:1 v:4] 包负重为2时最优结果物品组成:[w:2 v:5] 包负重为3时...
为此,我们定义一个二维数组,其中每个元素代表一个状态,即前个物体中若干个放入体积为背包中最大价值。数组为:,其中表示前件中若干个物品放入体积为的背包中的最大价值。 ②、初始状态 初始状态为和都为...
分支界限思想解0-1背包算法
背包问题九讲中的完全背包问题的三种算法的具体java实现代码。
背包问题