Table of Contents
1.Problem description
2.Implementation
3.Test
Home Java javaTutorial How to implement priority queue breadth first search algorithm in Java

How to implement priority queue breadth first search algorithm in Java

May 01, 2023 pm 09:46 PM
java

1.Problem description

How to implement priority queue breadth first search algorithm in Java

2.Implementation

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;
    }
}
Copy after login

3.Test

How to implement priority queue breadth first search algorithm in Java

The above is the detailed content of How to implement priority queue breadth first search algorithm in Java. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Square Root in Java Square Root in Java Aug 30, 2024 pm 04:26 PM

Guide to Square Root in Java. Here we discuss how Square Root works in Java with example and its code implementation respectively.

Perfect Number in Java Perfect Number in Java Aug 30, 2024 pm 04:28 PM

Guide to Perfect Number in Java. Here we discuss the Definition, How to check Perfect number in Java?, examples with code implementation.

Random Number Generator in Java Random Number Generator in Java Aug 30, 2024 pm 04:27 PM

Guide to Random Number Generator in Java. Here we discuss Functions in Java with examples and two different Generators with ther examples.

Weka in Java Weka in Java Aug 30, 2024 pm 04:28 PM

Guide to Weka in Java. Here we discuss the Introduction, how to use weka java, the type of platform, and advantages with examples.

Armstrong Number in Java Armstrong Number in Java Aug 30, 2024 pm 04:26 PM

Guide to the Armstrong Number in Java. Here we discuss an introduction to Armstrong's number in java along with some of the code.

Smith Number in Java Smith Number in Java Aug 30, 2024 pm 04:28 PM

Guide to Smith Number in Java. Here we discuss the Definition, How to check smith number in Java? example with code implementation.

Java Spring Interview Questions Java Spring Interview Questions Aug 30, 2024 pm 04:29 PM

In this article, we have kept the most asked Java Spring Interview Questions with their detailed answers. So that you can crack the interview.

Break or return from Java 8 stream forEach? Break or return from Java 8 stream forEach? Feb 07, 2025 pm 12:09 PM

Java 8 introduces the Stream API, providing a powerful and expressive way to process data collections. However, a common question when using Stream is: How to break or return from a forEach operation? Traditional loops allow for early interruption or return, but Stream's forEach method does not directly support this method. This article will explain the reasons and explore alternative methods for implementing premature termination in Stream processing systems. Further reading: Java Stream API improvements Understand Stream forEach The forEach method is a terminal operation that performs one operation on each element in the Stream. Its design intention is

See all articles