Bagaimana untuk melaksanakan algoritma Java BFS, DFS, pengaturcaraan dinamik dan algoritma tamak-javaTutorial-php.cn

Bagaimana untuk melaksanakan algoritma Java BFS, DFS, pengaturcaraan dinamik dan algoritma tamak

WBOY

Lepaskan： 2023-04-18 20:13:01

ke hadapan

998 orang telah melayarinya

Carian keluasan didahulukan

Algoritma carian didahulukan keluasan ialah algoritma yang merentasi atau mencari pokok atau graf Ia mencari dari nod akar dan mengembang ke bawah lapisan demi lapisan sehingga keadaan sasaran ditemui atau semua nod adalah Traverse. BFS biasanya dilaksanakan menggunakan baris gilir, yang meletakkan nod seterusnya ke dalam baris gilir setiap kali sehingga semua nod telah dilawati.

Berikut ialah pelaksanaan Java:

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.print(node.val + " ");

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}

Salin selepas log masuk

Carian mendalam-dahulu

Algoritma carian mendalam-dahulu ialah algoritma yang merentasi atau mencari pokok atau graf bermula dari nod akar Mula melintasi semua subpokok secara rekursif sehingga keadaan sasaran ditemui atau semua nod dilalui. DFS biasanya dilaksanakan menggunakan tindanan, yang menolak nod seterusnya ke tindanan setiap kali sehingga semua nod telah dilawati.

Berikut ialah pelaksanaan Java:

public void dfs(Node node, Set<Node> visited) {
    System.out.print(node.val + " ");
    visited.add(node);

    for (Node neighbor : node.neighbors) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

Salin selepas log masuk

Pengaturcaraan Dinamik

Algoritma pengaturcaraan dinamik (DP) ialah kaedah penyelesaian masalah yang digunakan untuk menyelesaikan sub- masalah dan masalah substruktur yang optimum. DP biasanya digunakan untuk menyelesaikan masalah pengoptimuman, seperti masalah laluan terpendek, masalah knapsack, dll.

Berikut ialah pelaksanaan Java:

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (weights[i - 1] <= j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}

Salin selepas log masuk

Rakus

Algoritma tamak ialah kaedah menyelesaikan masalah pengoptimuman yang sentiasa memilih penyelesaian optimum semasa. Tidak seperti pengaturcaraan dinamik, algoritma tamak tidak mempertimbangkan semua sub-masalah, tetapi hanya melihat pada penyelesaian optimum semasa.

Berikut ialah pelaksanaan Java:

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    Item[] items = new Item[n];

    for (int i = 0; i < n; i++) {
        items[i] = new Item(weights[i], values[i]);
    }

    Arrays.sort(items, (a, b) -> b.valuePerWeight - a.valuePerWeight);

    int totalValue = 0;
    int remainingCapacity = capacity;

    for (Item item : items) {
        if (remainingCapacity >= item.weight) {
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            totalValue += item.valuePerWeight * remainingCapacity;
            break;
        }
    }

    return totalValue;
}

class Item {
    int weight;
    int value;
    int valuePerWeight;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valuePerWeight = value / weight;
    }
}

Salin selepas log masuk

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma Java BFS, DFS, pengaturcaraan dinamik dan algoritma tamak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!