动态规划 中等难度 java 范例

动态规划是一种算法设计技术，通常用于优化涉及子问题重叠的问题。在 Java 中，它常用于解决最优化问题，比如斐波那契数列、背包问题或最长公共子序列等。下面是一个中等难度的 Java 动态规划示例，演示如何求解0-1背包问题：

public class Knapsack {
    public static int knapSack(int W, int wt[], int val[], int n) {
        // 创建一个二维数组 dp[n+1][W+1]，其中 dp[i][w]表示前i件物品放入总重量不超过w的背包所能获得的最大价值
        int[][] dp = new int[n + 1][W + 1];

        // 基本情况：当没有物品或背包容量为0时，最大价值为0
        for (int i = 0; i <= n; i++) {
            dp[i] = 0;
        }

        // 对于每种物品，考虑是否包含以及不包含两种情况
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (wt[i - 1] <= w) { // 如果当前物品能完全装入背包
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]); // 取当前物品和不包含当前物品的最大价值
                } else { // 当前物品无法完全装入，只能选择不放
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W]; // 返回最后的结果，即所有物品放入总重量不超过W的背包的最大价值
    }

    // 测试代码
    public static void main(String[] args) {
        int val[] = {60, 100, 120}; // 物品的价值
        int wt[] = {10, 20, 30}; // 物品的重量
        int W = 50; // 背包容量
        int n = val.length; // 物品数量
        System.out.println("最大价值: " + knapSack(W, wt, val, n));
    }
}

在这个例子中，`knapSack` 函数就是动态规划的核心，通过遍历物品和背包容量的可能性，逐步计算出最优解。相关问题：

1. 动态规划是如何解决重复子问题的？
2. 这段代码中的 `Math.max` 函数有什么作用？
3. 在实际应用中，动态规划有哪些其他常见的应用场景？