Java演算法之BFS,DFS,動態規劃與貪心演算法如何實現-java教程-PHP中文網

Java演算法之BFS,DFS,動態規劃與貪心演算法如何實現

WBOY

發布： 2023-04-18 20:13:01

轉載

1000 人瀏覽過

廣度優先搜尋

廣度優先搜尋演算法是一種遍歷或搜尋樹或圖的演算法，它從根節點開始搜尋並逐層向下擴展，直到找到目標狀態或所有節點都被遍歷。 BFS通常使用佇列來實現，它每次將下一個節點放入佇列中，直到所有的節點都被存取。

下面是一個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);
            }
        }
    }
}

登入後複製

深度優先搜尋

深度優先搜尋演算法是一種遍歷或搜尋樹或圖的演算法，它從根節點開始遞歸地遍歷所有子樹，直到找到目標狀態或所有節點都被遍歷。 DFS通常使用堆疊來實現，它每次將下一個節點壓入堆疊中，直到所有的節點都被存取。

下面是一個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);
        }
    }
}

登入後複製

動態規劃

動態規劃演算法（DP）是一種解決問題的方法，它用來解決重疊子問題和最優子結構問題。 DP通常用來解決最佳化問題，例如最短路徑問題、背包問題等。

下面是一個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];
}

登入後複製

貪心

貪心演算法是一種解決最佳化問題的方法，它總是選擇目前最優解。與動態規劃不同，貪心演算法並沒有考慮所有的子問題，而是只看當前的最優解。

下面是一個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;
    }
}

登入後複製

以上是Java演算法之BFS,DFS,動態規劃與貪心演算法如何實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！