Java数据结构算法-动态规划算法-Java实现动态规划算法

在Java中,我们可以使用动态规划算法来解决许多实际问题。例如,背包问题、最长公共子序列问题、最短路径问题等都可以通过动态规划算法得到高效的解决。在实现动态规划算法时,我们通常需要定义一个二维数组或一维数组来存储子问题的解,并通过迭代或递归的方式填充这个数组。以下是几个常见的动态规划问题的Java实现:
1. 0-1背包问题

public class KnapsackProblem {  
    public static int knapsack(int W, int wt[], int val[], int n) {  
        int i, w;  
        int K[][] = new int[n + 1][W + 1];  
  
        // Build table K[][] in bottom up manner  
        for (i = 0; i <= n; i++) {  
            for (w = 0; w <= W; w++) {  
                if (i == 0 || w == 0)  
                    K[i][w] = 0;  
                else if (wt[i - 1] <= w)  
                    K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);  
                else  
                    K[i][w] = K[i - 1][w];  
            }  
        }  
  
        return K[n][W];  
    }  
  
    public static void main(String args[]) {  
        int val[] = new int[] { 60, 100, 120 };  
        int wt[] = new int[] { 10, 20, 30 };  
        int W = 50;  
        int n = val.length;  
        System.out.println(knapsack(W, wt, val, n));  
    }  
}

2. 最长公共子序列(LCS)

public class LongestCommonSubsequence {  
    static int lcs(char X[], char Y[], int m, int n) {  
        int L[][] = new int[m + 1][n + 1];  
        int i, j;  
  
        for (i = 0; i <= m; i++) {  
            for (j = 0; j <= n; j++) {  
                if (i == 0 || j == 0)  
                    L[i][j] = 0;  
                else if (X[i - 1] == Y[j - 1])  
                    L[i][j] = L[i - 1][j - 1] + 1;  
                else  
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);  
            }  
        }  
  
        return L[m][n];  
    }  
  
    public static void main(String args[]) {  
        char X[] = "AGGTAB".toCharArray();  
        char Y[] = "GXTXAYB".toCharArray();  
        int m = X.length;  
        int n = Y.length;  
        System.out.println("Length of LCS is " + lcs(X, Y, m, n));  
    }  
}

3. 最短路径问题(Dijkstra算法)

import java.util.*;  
  
public class Dijkstra {  
    static final int INF = 99999, V = 9;  
  
    void printSolution(int dist[]) {  
        System.out.println("Vertex \t\t Distance from Source");  
        for (int i = 0; i < V; ++i)  
            System.out.println(i + "\t\t" + dist[i]);  
    }  
  
    void dijkstra(int graph[][], int src) {  
        int dist[] = new int[V];  
        boolean sptSet[] = new boolean[V];  
  
        for (int i = 0; i < V; i++)  
            dist[i] = INF, sptSet[i] = false;  
  
        dist[src] = 0;  
  
        for (int count = 0; count < V - 1; count++) {  
            int u = minDistance(dist, sptSet);  
  
            sptSet[u] = true;  
  
            for (int v = 0; v < V; v++)  
  
                if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])  
                    dist[v] = dist[u] + graph[u][v];
上一篇:Swift:在 Win10 上编程入门


下一篇:为什么要学习大模型应用开发?