Javaで優先キュー幅優先検索アルゴリズムを実装する方法
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で優先キュー幅優先検索アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック









Java の Weka へのガイド。ここでは、weka java の概要、使い方、プラットフォームの種類、利点について例を交えて説明します。

この記事では、Java Spring の面接で最もよく聞かれる質問とその詳細な回答をまとめました。面接を突破できるように。

Java 8は、Stream APIを導入し、データ収集を処理する強力で表現力のある方法を提供します。ただし、ストリームを使用する際の一般的な質問は次のとおりです。 従来のループにより、早期の中断やリターンが可能になりますが、StreamのForeachメソッドはこの方法を直接サポートしていません。この記事では、理由を説明し、ストリーム処理システムに早期終了を実装するための代替方法を調査します。 さらに読み取り:JavaストリームAPIの改善 ストリームを理解してください Foreachメソッドは、ストリーム内の各要素で1つの操作を実行する端末操作です。その設計意図はです

Java での日付までのタイムスタンプに関するガイド。ここでは、Java でタイムスタンプを日付に変換する方法とその概要について、例とともに説明します。

カプセルは3次元の幾何学的図形で、両端にシリンダーと半球で構成されています。カプセルの体積は、シリンダーの体積と両端に半球の体積を追加することで計算できます。このチュートリアルでは、さまざまな方法を使用して、Javaの特定のカプセルの体積を計算する方法について説明します。 カプセルボリュームフォーミュラ カプセルボリュームの式は次のとおりです。 カプセル体積=円筒形の体積2つの半球体積 で、 R:半球の半径。 H:シリンダーの高さ(半球を除く)。 例1 入力 RADIUS = 5ユニット 高さ= 10単位 出力 ボリューム= 1570.8立方ユニット 説明する 式を使用してボリュームを計算します。 ボリューム=π×R2×H(4

Java は、初心者と経験豊富な開発者の両方が学習できる人気のあるプログラミング言語です。このチュートリアルは基本的な概念から始まり、高度なトピックに進みます。 Java Development Kit をインストールしたら、簡単な「Hello, World!」プログラムを作成してプログラミングを練習できます。コードを理解したら、コマンド プロンプトを使用してプログラムをコンパイルして実行すると、コンソールに「Hello, World!」と出力されます。 Java の学習はプログラミングの旅の始まりであり、習熟が深まるにつれて、より複雑なアプリケーションを作成できるようになります。
