Table des matières
1.Description du problème
2.Mise en œuvre
3.Test
Maison Java javaDidacticiel Comment implémenter l'algorithme de recherche prioritaire en largeur de file d'attente en Java

Comment implémenter l'algorithme de recherche prioritaire en largeur de file d'attente en Java

May 01, 2023 pm 09:46 PM
java

1.Description du problème

Comment implémenter lalgorithme de recherche prioritaire en largeur de file dattente en Java

2.Mise en œuvre

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;
    }
}
Copier après la connexion

3.Test

Comment implémenter lalgorithme de recherche prioritaire en largeur de file dattente en Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Racine carrée en Java Racine carrée en Java Aug 30, 2024 pm 04:26 PM

Guide de la racine carrée en Java. Nous discutons ici du fonctionnement de Square Root en Java avec un exemple et son implémentation de code respectivement.

Nombre parfait en Java Nombre parfait en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre parfait en Java. Nous discutons ici de la définition, comment vérifier le nombre parfait en Java ?, des exemples d'implémentation de code.

Générateur de nombres aléatoires en Java Générateur de nombres aléatoires en Java Aug 30, 2024 pm 04:27 PM

Guide du générateur de nombres aléatoires en Java. Nous discutons ici des fonctions en Java avec des exemples et de deux générateurs différents avec d'autres exemples.

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

Guide de Weka en Java. Nous discutons ici de l'introduction, de la façon d'utiliser Weka Java, du type de plate-forme et des avantages avec des exemples.

Numéro Armstrong en Java Numéro Armstrong en Java Aug 30, 2024 pm 04:26 PM

Guide du numéro Armstrong en Java. Nous discutons ici d'une introduction au numéro d'Armstrong en Java ainsi que d'une partie du code.

Numéro de Smith en Java Numéro de Smith en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre de Smith en Java. Nous discutons ici de la définition, comment vérifier le numéro Smith en Java ? exemple avec implémentation de code.

Questions d'entretien chez Java Spring Questions d'entretien chez Java Spring Aug 30, 2024 pm 04:29 PM

Dans cet article, nous avons conservé les questions d'entretien Java Spring les plus posées avec leurs réponses détaillées. Pour que vous puissiez réussir l'interview.

Break or Return of Java 8 Stream Forach? Break or Return of Java 8 Stream Forach? Feb 07, 2025 pm 12:09 PM

Java 8 présente l'API Stream, fournissant un moyen puissant et expressif de traiter les collections de données. Cependant, une question courante lors de l'utilisation du flux est: comment se casser ou revenir d'une opération FOREAK? Les boucles traditionnelles permettent une interruption ou un retour précoce, mais la méthode Foreach de Stream ne prend pas directement en charge cette méthode. Cet article expliquera les raisons et explorera des méthodes alternatives pour la mise en œuvre de terminaison prématurée dans les systèmes de traitement de flux. Lire plus approfondie: Améliorations de l'API Java Stream Comprendre le flux Forach La méthode foreach est une opération terminale qui effectue une opération sur chaque élément du flux. Son intention de conception est

See all articles