在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];