Java实现优先队列式广度优先搜索算法的示例代码
更新时间:2022年8月21日 16:36 点击:293 作者:chengqiuming
1.问题描述
2.实现
package com.platform.modules.alg.alglib.p933; import java.util.Arrays; import java.util.PriorityQueue; public class P933 { public static final int N = 10; // 记录最优解 boolean bestx[] = new boolean[N]; // 辅助数组,用于存储排序后的重量和价值 private int w[] = new int[N]; private int v[] = new int[N]; Goods goods[] = new Goods[N]; Object S[] = new Object[N]; // 用来记录最优解 Integer bestp; // 为背包的最大容量 int W; // 为物品的个数。 int n; // 为所有物品的总重量。 int sumw; // 为所有物品的总价值 int sumv; public String output = ""; public P933() { for (int i = 0; i < goods.length; i++) { goods[i] = new Goods(); } for (int i = 0; i < S.length; i++) { S[i] = new Object(); } } // 计算节点的上界 double Bound(Node tnode) { // 已装入背包物品价值 double maxvalue = tnode.cp; int t = tnode.id; // 排序后序号 double left = tnode.rw; // 剩余容量 while (t <= n && w[t] <= left) { maxvalue += v[t]; left -= w[t++]; } if (t <= n) maxvalue += ((double) (v[t])) / w[t] * left; return maxvalue; } public String cal(String input) { String[] line = input.split("\n"); String[] words = line[0].split(" "); // 物品的个数和背包的容量 n = Integer.parseInt(words[0]); W = Integer.parseInt(words[1]); bestp = 0; // 用来记录最优解 sumw = 0; // sumw 为所有物品的总重量。 sumv = 0; // sumv为所有物品的总价值 words = line[1].split(" "); for (int i = 1; i <= words.length / 2; i++) { // 输入每个物品的重量和价值,用空格分开 goods[i].weight = Integer.parseInt(words[2 * i - 2]); goods[i].value = Integer.parseInt(words[2 * i - 1]); sumw += goods[i].weight; sumv += goods[i].value; S[i - 1].id = i; S[i - 1].d = 1.0 * goods[i].value / goods[i].weight; } if (sumw <= W) { bestp = sumv; output = bestp.toString(); return output; } Arrays.sort(S); // 按价值重量比非递增排序 for (int i = 1; i <= n; i++) {//把排序后的数据传递给辅助数组 w[i] = goods[S[i - 1].id].weight; v[i] = goods[S[i - 1].id].value; } priorbfs();//优先队列分支限界法 output += bestp + "\n"; for (int i = 1; i <= n; i++) { // 输出最优解 if (bestx[i]) output += S[i - 1].id + " "; // 输出原物品序号(排序前的) } return output; } // 优先队列式分支限界法 int priorbfs() { // 当前处理的物品序号t,当前装入背包物品价值tcp,当前剩余容量trw int t, tcp, trw; double tup; // 当前价值上界 tup PriorityQueue<Node> q = new PriorityQueue<>(); // 优先队列 q.add(new Node(0, sumv, W, 1)); // 初始化,根结点加入优先队列 while (!q.isEmpty()) { // 定义三个结点型变量 Node livenode; Node lchild = new Node(); Node rchild = new Node(); livenode = q.peek(); // 取出队头元素作为当前扩展结点 livenode q.poll(); // 队头元素出队 t = livenode.id; // 当前处理的物品序号 // 搜到最后一个物品的时候不需要往下搜索。 // 如果当前的背包没有剩余容量(已经装满)了,不再扩展。 if (t > n || livenode.rw == 0) { if (livenode.cp >= bestp) { // 更新最优解和最优值 for (int i = 1; i <= n; i++) bestx[i] = livenode.x[i]; bestp = livenode.cp; } continue; } if (livenode.up < bestp)//如果不满足不再扩展 continue; tcp = livenode.cp; //当前背包中的价值 trw = livenode.rw; //背包剩余容量 if (trw >= w[t]) { //扩展左孩子,满足约束条件,可以放入背包 lchild.cp = tcp + v[t]; lchild.rw = trw - w[t]; lchild.id = t + 1; tup = Bound(lchild); //计算左孩子上界 lchild = new Node(lchild.cp, tup, lchild.rw, lchild.id); for (int i = 1; i <= n; i++)//复制以前的解向量 lchild.x[i] = livenode.x[i]; lchild.x[t] = true; if (lchild.cp > bestp)//比最优值大才更新 bestp = lchild.cp; q.add(lchild);//左孩子入队 } rchild.cp = tcp; rchild.rw = trw; rchild.id = t + 1; tup = Bound(rchild);//计算右孩子上界 if (tup >= bestp) {//扩展右孩子,满足限界条件,不放入 rchild = new Node(tcp, tup, trw, t + 1); for (int i = 1; i <= n; i++)//复制以前的解向量 rchild.x[i] = livenode.x[i]; rchild.x[t] = false; q.add(rchild);//右孩子入队 } } return bestp;//返回最优值。 } } // 定义结点。每个节点来记录当前的解。 class Node implements Comparable<Node> { int cp; // cp 为当前装入背包的物品总价值 double up; // 价值上界 int rw; // 剩余容量 int id; // 物品号 boolean x[] = new boolean[P933.N]; // 解向量 Node() { } Node(int _cp, double _up, int _rw, int _id) { cp = _cp; up = _up; rw = _rw; id = _id; } @Override public int compareTo(Node o) { return (this.up - o.up) > 0 ? 1 : -1; } } // 物品 class Goods { int weight; // 重量 int value; // 价值 } // 辅助物品结构体,用于按单位重量价值(价值/重量比)排序 class Object implements Comparable { int id; // 序号 double d; // 单位重量价值 @Override public int compareTo(java.lang.Object o) { return this.d > ((Object) o).d ? -1 : 1; } }
3.测试
到此这篇关于Java实现优先队列式广度优先搜索算法的示例代码的文章就介绍到这了,更多相关Java广度优先搜索算法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/chengqiuming/article/details/126439359
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13