- 浏览: 323002 次
- 性别:
- 来自: 西宁
文章分类
- 全部博客 (120)
- Java Thought (29)
- Java Pattern (4)
- Data Base (7)
- Algorithm Design (33)
- Linux (0)
- Mysql (2)
- Oracle (0)
- ConstructionDesign-架构 (5)
- Spring Platform (0)
- Tomcat (1)
- JavaScript (7)
- Web System (3)
- MS SQLServer (1)
- 软件哲学 (6)
- View (3)
- Java GUI (4)
- CSSDIV (7)
- CloudComputing (0)
- WebService (0)
- SystemOrProject (2)
- SOA (0)
- 互转共享 (3)
- 偶尔java习题 (0)
- Thinks with does (1)
最新评论
-
sassds:
佩服啊 高手
分享一款js特效 -
bhjackson:
学习啦,能否详细介绍下回溯的过程?O(∩_∩)O谢谢
分享回溯法- 找n个数中r个数的组合 -
zk7019311:
了解了解。。。。。
业务层代码复用的一点建议 -
lijie1819:
看到LZ的设计思想,感觉和抽象工厂模式有点相像。
业务层代码复用的一点建议 -
wjjcml1982:
酷毙了!楼主太强悍了!
分享一款js特效
1. 问题描述
给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为c。问:应该如何选择装入背包的物品,使得装入
背包中物品的总价值最大?
2. 问题分析
在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。该问题是子集选取问题。因此解空间可用子集书
来表示。
在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。
设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r <= bestp时,可剪去右子树。
计算右子树中解的上界的更好的方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分
而装满背包。由此得到的价值是右子树中解的上界。
3. 举例子说明:
n = 4;
c = 7;
pi = [9, 10, 7, 4];
wi = [3, 5, 2 ,1];
单位重量价值分别为[3, 2, 3.5, 4];
则以物品单位重量价值的递减顺序装入物品。先装入物品4, 然后装入物品3, 再装入物品1, 则背包容量剩余为:7-(1+2+3)=1.
最后只能只能装入1/5 = 0.2的物品2。由此得到一个解为x=[1,0.2,1,1],其相应的价值为22.因此,对于这个实例,最优值不超过22.
4. Java实现
给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为c。问:应该如何选择装入背包的物品,使得装入
背包中物品的总价值最大?
2. 问题分析
在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。该问题是子集选取问题。因此解空间可用子集书
来表示。
在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。
设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。当cp+r <= bestp时,可剪去右子树。
计算右子树中解的上界的更好的方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分
而装满背包。由此得到的价值是右子树中解的上界。
3. 举例子说明:
n = 4;
c = 7;
pi = [9, 10, 7, 4];
wi = [3, 5, 2 ,1];
单位重量价值分别为[3, 2, 3.5, 4];
则以物品单位重量价值的递减顺序装入物品。先装入物品4, 然后装入物品3, 再装入物品1, 则背包容量剩余为:7-(1+2+3)=1.
最后只能只能装入1/5 = 0.2的物品2。由此得到一个解为x=[1,0.2,1,1],其相应的价值为22.因此,对于这个实例,最优值不超过22.
4. Java实现
package com.maozj.suanfa; import java.util.Arrays; /** * 0 1背包问题回溯算法 * * @since jdk1.5以上 * @author 毛正吉 * @version 1.0 * @date 2010.05.22 */ public class ZeroOneQuestion { /** * @param args */ public static void main(String[] args) { double[] pp = { 0, 9, 10, 7, 4 }; double[] ww = { 0, 3, 5, 2, 1 }; double cc = 7.0; double result = zeroOneQuestion(pp, ww, cc); System.out.println("result=" + result); } private static class Element implements Comparable { int id; // 物品编号 double dv; // 单位重量价值 private Element(int _id, double _dv) { id = _id; dv = _dv; } public int compareTo(Object o) { int res = 0; double d = ((Element) o).dv; if (dv < d) { res = -1; } else if (dv == d) { res = 0; } else { res = 1; } return res; } public boolean equals(Object o) { return (dv == ((Element) o).dv); } public String toString() { return "id=" + id + ", dv=" + dv; } } static double c; // 背包容量 static int n; // 物品数 static double[] w; // 物品重量数组 static double[] p; // 物品价值数组 static double cw; // 当前重量 static double cp; // 当前价值 static double bestp;// 当前最优价值 public static double zeroOneQuestion(double[] pp, double[] ww, double cc) { c = cc; n = pp.length - 1; cw = 0.0; cp = 0.0; bestp = 0.0; // q为单位重量价值数组 Element[] q = new Element[n]; Element[] qq = new Element[n]; // 初始化q[0, n-1] for (int i = 1; i <= n; i++) { q[i - 1] = new Element(i, pp[i] / ww[i]); } // 将各物品依单位重量价值从大到小排序 Arrays.sort(q); for (int i = 0; i < n; i++) { qq[i] = q[n - i - 1]; } for (int i = 0; i < n; i++) { System.out.println(qq[i]); } System.out.println(); System.out.println("################################"); p = new double[n + 1]; w = new double[n + 1]; for (int i = 1; i <= n; i++) { p[i] = pp[qq[i-1].id]; w[i] = ww[qq[i-1].id]; } for (int i = 1; i <= n; i++) { System.out.print(p[i] + " "); } System.out.println(); for (int i = 1; i <= n; i++) { System.out.print(w[i] + " "); } System.out.println(); // 回溯搜索 backtrack(1); return bestp; } private static void backtrack(int i) { if (i > n) { bestp = cp; return; } // 搜索子树 if (cw + w[i] <= c) { // 进入左子树 cw += w[i]; cp += p[i]; backtrack(i + 1); cw -= w[i]; cp -= p[i]; } if (bound(i + 1) > bestp) { // 进入右子树 backtrack(i + 1); } } /** * 计算上界 * * @param i * @return */ private static double bound(int i) { double cleft = c - cw; // 剩余容量 double bound = cp; // 以物品单位重量价值递减顺序装入物品 while ((i <= n) && (w[i] <= cleft)) { cleft -= w[i]; bound += p[i]; i++; } // 装满背包 if (i <= n) { bound += p[i] / w[i] * cleft; } return bound; } }
发表评论
-
开散列的简单模拟(一)
2010-06-28 08:33 18081. 散列 散列有两种 ... -
递归和动态规划构造两个字符序列的最长公共字符子序列
2010-06-28 08:28 4484应je朋友要求,所以翻开以前的算法题目,整理了以下,给 ... -
最大公约数的应用 - 分享
2010-06-25 08:08 18301.先看一家大公司笔试题 数组中有n个数据,要将它们顺 ... -
信息数字化解逻辑题分享
2010-06-21 08:09 12441. 前提条件: 将逻辑题目中的信息用数字化描述。 ... -
递归算法分析-分享
2010-06-19 16:09 15711. 深入认识递归 (1) 递 ... -
非递归算法分析实例分享
2010-06-18 15:47 10451 仅仅依赖于问题规模的时间复杂度 (1) 例1: 交换i和 ... -
NP完全性问题
2010-06-18 14:02 6999在学习算法设计与分析时,经常会提到NP完全性问题,到底 ... -
算法分析精述分享
2010-06-18 12:03 8611. 算法分析的评价体系 评价算法的三条主要标准是: ... -
贪婪策略算法的总结分享
2010-06-11 08:30 60481. 贪婪算法描述 贪婪算法又叫登山法,它的根本思想是 ... -
带权有向图 - 边上权值非负情形的单源最短路径问题
2010-06-07 08:57 26621. 问题描述: 给定 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)四
2010-06-07 08:54 135421. 工作分配问题。 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)三
2010-06-07 08:53 108017. 字符统计问题。 编写一个算法,统计在一个输入 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)二
2010-06-07 08:47 13508. 数字迷问题。 A B C ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)一
2010-06-07 08:38 11681. 线程问题。 设计4个线程,其中两个线程每次对j增加 ... -
是否很久没抽象和逻辑了呢? DODO它吧(很基础)
2010-06-07 08:37 18661. 线程问题。 设计 ... -
Java快速排序算法整理(二)
2010-05-31 14:04 1024package boke.sort; /** * 快 ... -
Java快速排序算法整理(一)
2010-05-31 13:39 649package boke.sort; /** * 快 ... -
Java最小堆实现
2010-05-31 08:29 58331.堆结点 package boke.heap1; /* ... -
Java插入排序代码整理
2010-05-28 14:44 1238package boke.sort; /** * 插 ... -
Java选择排序代码整理
2010-05-28 14:37 1498package boke.sort; /** * 选 ...
相关推荐
基于协同过滤算法的电影推荐系统的部署与应用,将对首页,个人中心,用户管理,电影分类管理,免费电影管理,付费电影管理,电影订单管理,我的电影管理,电影论坛,系统管理等功能进行管理 项目关键技术 开发工具:IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7+ 后端技术:ssm 前端技术:Vue 关键技术:springboot、SSM、vue、MYSQL、MAVEN 数据库工具:Navicat、SQLyog
12345688882222
微软演示材料
1、开发环境:ssm框架;内含Mysql数据库;JSP技术 2、需要项目部署的可以私信 3、项目代码都经过严格调试,代码没有任何bug! 4、该资源包括项目的全部源码,下载可以直接使用! 5、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。 6、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。
采用后端Laravel框架进行开发,前端开发框架则使用了uniapp+vue。在环境配置方面,我们建议使用php7.4 + mysql5.6 + nginx1.22 + redis,并且推荐使用宝塔面板或lnmp等工具进行配置。
1、开发环境:ssm框架;内含Mysql数据库;JSP技术 2、需要项目部署的可以私信 3、项目代码都经过严格调试,代码没有任何bug! 4、该资源包括项目的全部源码,下载可以直接使用! 5、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。 6、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。
matlab
1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。
FlutterFire 是一组Flutter 插件 ,可让 Flutter 应用使用Firebase服务。您可以按照Firebase for Flutter代码实验室中的示例了解如何使用这些插件。 Flutter是 Google 的 UI 工具包,可用于通过单一代码库为移动设备、网页和桌面构建精美的原生编译应用。Flutter 被世界各地的开发者和组织使用,并且是免费且开源的。
小程序-祝福话(源码).zip 小程序-祝福话(源码).zip 小程序-祝福话(源码).zip
1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。
构建使用jQuery组件DataTables.net的Asp.Net 8 MVC应用程序的实用指南。
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
c++课程设计-个人收支管理系统.7z
Centos7_shell脚本一键安装httpd_nginx_php_jdk_kafka_psql__bash-shell
1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。