Java實(shí)現(xiàn)優(yōu)先隊(duì)列式廣度優(yōu)先搜索算法的示例代碼
1.問(wèn)題描述
2.實(shí)現(xiàn)
package com.platform.modules.alg.alglib.p933; import java.util.Arrays; import java.util.PriorityQueue; public class P933 { public static final int N = 10; // 記錄最優(yōu)解 boolean bestx[] = new boolean[N]; // 輔助數(shù)組,用于存儲(chǔ)排序后的重量和價(jià)值 private int w[] = new int[N]; private int v[] = new int[N]; Goods goods[] = new Goods[N]; Object S[] = new Object[N]; // 用來(lái)記錄最優(yōu)解 Integer bestp; // 為背包的最大容量 int W; // 為物品的個(gè)數(shù)。 int n; // 為所有物品的總重量。 int sumw; // 為所有物品的總價(jià)值 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(); } } // 計(jì)算節(jié)點(diǎn)的上界 double Bound(Node tnode) { // 已裝入背包物品價(jià)值 double maxvalue = tnode.cp; int t = tnode.id; // 排序后序號(hào) 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(" "); // 物品的個(gè)數(shù)和背包的容量 n = Integer.parseInt(words[0]); W = Integer.parseInt(words[1]); bestp = 0; // 用來(lái)記錄最優(yōu)解 sumw = 0; // sumw 為所有物品的總重量。 sumv = 0; // sumv為所有物品的總價(jià)值 words = line[1].split(" "); for (int i = 1; i <= words.length / 2; i++) { // 輸入每個(gè)物品的重量和價(jià)值,用空格分開(kā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); // 按價(jià)值重量比非遞增排序 for (int i = 1; i <= n; i++) {//把排序后的數(shù)據(jù)傳遞給輔助數(shù)組 w[i] = goods[S[i - 1].id].weight; v[i] = goods[S[i - 1].id].value; } priorbfs();//優(yōu)先隊(duì)列分支限界法 output += bestp + "\n"; for (int i = 1; i <= n; i++) { // 輸出最優(yōu)解 if (bestx[i]) output += S[i - 1].id + " "; // 輸出原物品序號(hào)(排序前的) } return output; } // 優(yōu)先隊(duì)列式分支限界法 int priorbfs() { // 當(dāng)前處理的物品序號(hào)t,當(dāng)前裝入背包物品價(jià)值tcp,當(dāng)前剩余容量trw int t, tcp, trw; double tup; // 當(dāng)前價(jià)值上界 tup PriorityQueue<Node> q = new PriorityQueue<>(); // 優(yōu)先隊(duì)列 q.add(new Node(0, sumv, W, 1)); // 初始化,根結(jié)點(diǎn)加入優(yōu)先隊(duì)列 while (!q.isEmpty()) { // 定義三個(gè)結(jié)點(diǎn)型變量 Node livenode; Node lchild = new Node(); Node rchild = new Node(); livenode = q.peek(); // 取出隊(duì)頭元素作為當(dāng)前擴(kuò)展結(jié)點(diǎn) livenode q.poll(); // 隊(duì)頭元素出隊(duì) t = livenode.id; // 當(dāng)前處理的物品序號(hào) // 搜到最后一個(gè)物品的時(shí)候不需要往下搜索。 // 如果當(dāng)前的背包沒(méi)有剩余容量(已經(jīng)裝滿)了,不再擴(kuò)展。 if (t > n || livenode.rw == 0) { if (livenode.cp >= bestp) { // 更新最優(yōu)解和最優(yōu)值 for (int i = 1; i <= n; i++) bestx[i] = livenode.x[i]; bestp = livenode.cp; } continue; } if (livenode.up < bestp)//如果不滿足不再擴(kuò)展 continue; tcp = livenode.cp; //當(dāng)前背包中的價(jià)值 trw = livenode.rw; //背包剩余容量 if (trw >= w[t]) { //擴(kuò)展左孩子,滿足約束條件,可以放入背包 lchild.cp = tcp + v[t]; lchild.rw = trw - w[t]; lchild.id = t + 1; tup = Bound(lchild); //計(jì)算左孩子上界 lchild = new Node(lchild.cp, tup, lchild.rw, lchild.id); for (int i = 1; i <= n; i++)//復(fù)制以前的解向量 lchild.x[i] = livenode.x[i]; lchild.x[t] = true; if (lchild.cp > bestp)//比最優(yōu)值大才更新 bestp = lchild.cp; q.add(lchild);//左孩子入隊(duì) } rchild.cp = tcp; rchild.rw = trw; rchild.id = t + 1; tup = Bound(rchild);//計(jì)算右孩子上界 if (tup >= bestp) {//擴(kuò)展右孩子,滿足限界條件,不放入 rchild = new Node(tcp, tup, trw, t + 1); for (int i = 1; i <= n; i++)//復(fù)制以前的解向量 rchild.x[i] = livenode.x[i]; rchild.x[t] = false; q.add(rchild);//右孩子入隊(duì) } } return bestp;//返回最優(yōu)值。 } } // 定義結(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)來(lái)記錄當(dāng)前的解。 class Node implements Comparable<Node> { int cp; // cp 為當(dāng)前裝入背包的物品總價(jià)值 double up; // 價(jià)值上界 int rw; // 剩余容量 int id; // 物品號(hào) 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; // 價(jià)值 } // 輔助物品結(jié)構(gòu)體,用于按單位重量?jī)r(jià)值(價(jià)值/重量比)排序 class Object implements Comparable { int id; // 序號(hào) double d; // 單位重量?jī)r(jià)值 @Override public int compareTo(java.lang.Object o) { return this.d > ((Object) o).d ? -1 : 1; } }
3.測(cè)試
到此這篇關(guān)于Java實(shí)現(xiàn)優(yōu)先隊(duì)列式廣度優(yōu)先搜索算法的示例代碼的文章就介紹到這了,更多相關(guān)Java廣度優(yōu)先搜索算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java中的HashMap為什么會(huì)產(chǎn)生死循環(huán)
這篇文章主要介紹了Java中的HashMap為什么會(huì)產(chǎn)生死循環(huán),HashMap?死循環(huán)是一個(gè)比較常見(jiàn)、比較經(jīng)典的問(wèn)題,下面文章我們就來(lái)徹底理解死循環(huán)的原因。需要的小伙伴可以參考一下2022-05-05springmvc和js前端的數(shù)據(jù)傳遞和接收方式(兩種)
本文介紹了springmvc和js前端的數(shù)據(jù)傳遞和接收方式(兩種),詳細(xì)的介紹了兩種方式,一種是json格式傳遞,另一種是Map傳遞,具有一定的參考價(jià)值,有興趣的可以了解一下2017-12-12SpringSecurity中@PermitAll與@PreAuthorize的實(shí)現(xiàn)
@PermitAll和@PreAuthorize都是處理安全性的強(qiáng)大工具,本文主要介紹了SpringSecurity中@PermitAll與@PreAuthorize的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-07-07在idea中將java項(xiàng)目中的單個(gè)類打包成jar包操作
這篇文章主要介紹了在idea中將java項(xiàng)目中的單個(gè)類打包成jar包操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08Mybatis Generator Plugin悲觀鎖實(shí)現(xiàn)示例
本文將從悲觀鎖為例,讓你快速了解如何實(shí)現(xiàn)Mybatis Generator Plugin。文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-09-09