欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實現(xiàn)優(yōu)先隊列式廣度優(yōu)先搜索算法的示例代碼

 更新時間:2022年08月21日 09:47:51   作者:chengqiuming  
這篇文章主要為大家詳細介紹了Java如何實現(xiàn)優(yōu)先隊列式廣度優(yōu)先搜索算法,文中通過一個示例帶大家具體了解了實現(xiàn)的方法,需要的可以參考一下

1.問題描述

2.實現(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ù)組,用于存儲排序后的重量和價值
    private int w[] = new int[N];
    private int v[] = new int[N];
    Goods goods[] = new Goods[N];
    Object S[] = new Object[N];
    // 用來記錄最優(yōu)解
    Integer bestp;
    // 為背包的最大容量
    int W;
    // 為物品的個數(shù)。
    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();
        }
    }
 
    // 計算節(jié)點的上界
    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(" ");
        // 物品的個數(shù)和背包的容量
        n = Integer.parseInt(words[0]);
        W = Integer.parseInt(words[1]);
        bestp = 0; // 用來記錄最優(yōu)解
        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++) {//把排序后的數(shù)據(jù)傳遞給輔助數(shù)組
            w[i] = goods[S[i - 1].id].weight;
            v[i] = goods[S[i - 1].id].value;
        }
        priorbfs();//優(yōu)先隊列分支限界法
        output += bestp + "\n";
 
        for (int i = 1; i <= n; i++) { // 輸出最優(yōu)解
            if (bestx[i])
                output += S[i - 1].id + " "; // 輸出原物品序號(排序前的)
        }
        return output;
    }
 
    // 優(yōu)先隊列式分支限界法
    int priorbfs() {
        // 當前處理的物品序號t,當前裝入背包物品價值tcp,當前剩余容量trw
        int t, tcp, trw;
        double tup;  // 當前價值上界 tup
        PriorityQueue<Node> q = new PriorityQueue<>(); // 優(yōu)先隊列
 
        q.add(new Node(0, sumv, W, 1)); // 初始化,根結(jié)點加入優(yōu)先隊列
        while (!q.isEmpty()) {
            // 定義三個結(jié)點型變量
            Node livenode;
            Node lchild = new Node();
            Node rchild = new Node();
            livenode = q.peek(); // 取出隊頭元素作為當前擴展結(jié)點 livenode
            q.poll(); // 隊頭元素出隊
            t = livenode.id; // 當前處理的物品序號
            // 搜到最后一個物品的時候不需要往下搜索。
            // 如果當前的背包沒有剩余容量(已經(jīng)裝滿)了,不再擴展。
            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)//如果不滿足不再擴展
                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)//比最優(yōu)值大才更新
                    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;//返回最優(yōu)值。
    }
}
 
// 定義結(jié)點。每個節(jié)點來記錄當前的解。
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; // 價值
}
 
// 輔助物品結(jié)構(gòu)體,用于按單位重量價值(價值/重量比)排序
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.測試

到此這篇關(guān)于Java實現(xiàn)優(yōu)先隊列式廣度優(yōu)先搜索算法的示例代碼的文章就介紹到這了,更多相關(guān)Java廣度優(yōu)先搜索算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java中的HashMap為什么會產(chǎn)生死循環(huán)

    Java中的HashMap為什么會產(chǎn)生死循環(huán)

    這篇文章主要介紹了Java中的HashMap為什么會產(chǎn)生死循環(huán),HashMap?死循環(huán)是一個比較常見、比較經(jīng)典的問題,下面文章我們就來徹底理解死循環(huán)的原因。需要的小伙伴可以參考一下
    2022-05-05
  • springmvc和js前端的數(shù)據(jù)傳遞和接收方式(兩種)

    springmvc和js前端的數(shù)據(jù)傳遞和接收方式(兩種)

    本文介紹了springmvc和js前端的數(shù)據(jù)傳遞和接收方式(兩種),詳細的介紹了兩種方式,一種是json格式傳遞,另一種是Map傳遞,具有一定的參考價值,有興趣的可以了解一下
    2017-12-12
  • icePDF去水印的方法(推薦)

    icePDF去水印的方法(推薦)

    下面小編就為大家?guī)硪黄猧cePDF去水印的方法(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • 詳解idea打包jar的多種方式

    詳解idea打包jar的多種方式

    本篇文章總結(jié)出用IDEA打包jar包的多種方式。項目打包Jar包可以參考如下形式:用IDEA自帶的打包形式;用Maven插件maven-shade-plugin打包;用Maven插件maven-assembly-plugin打包。下面跟著小編一起來看下吧
    2017-01-01
  • 實例講解JAVA 模板方法模式

    實例講解JAVA 模板方法模式

    這篇文章主要介紹了JAVA 模板方法模式的的相關(guān)資料,文中示例代碼非常細致,幫助大家更好的理解和學習,感興趣的朋友可以了解下
    2020-06-06
  • SpringSecurity中@PermitAll與@PreAuthorize的實現(xiàn)

    SpringSecurity中@PermitAll與@PreAuthorize的實現(xiàn)

    @PermitAll和@PreAuthorize都是處理安全性的強大工具,本文主要介紹了SpringSecurity中@PermitAll與@PreAuthorize的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2024-07-07
  • HashMap插入相同key問題

    HashMap插入相同key問題

    這篇文章主要介紹了HashMap插入相同key問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-05-05
  • 在idea中將java項目中的單個類打包成jar包操作

    在idea中將java項目中的單個類打包成jar包操作

    這篇文章主要介紹了在idea中將java項目中的單個類打包成jar包操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-08-08
  • Spring JPA自定義查詢結(jié)果的接收方式

    Spring JPA自定義查詢結(jié)果的接收方式

    這篇文章主要介紹了Spring JPA自定義查詢結(jié)果的接收方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • Mybatis Generator Plugin悲觀鎖實現(xiàn)示例

    Mybatis Generator Plugin悲觀鎖實現(xiàn)示例

    本文將從悲觀鎖為例,讓你快速了解如何實現(xiàn)Mybatis Generator Plugin。文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-09-09

最新評論