01背包问题动态规划java

下面是01背包问题的动态规划Java代码实现：

public class KnapsackProblem {
    public static void main(String[] args) {
        // 物品重量
        int[] w = {1, 4, 3};
        // 物品价值
        int[] v = {1500, 3000, 2000};
        // 背包容量
        int capacity = 4;
        // 物品个数
        int n = w.length;

        // 创建二维数组，表示表格
        int[][] dp = new int[n + 1][capacity + 1];

        // 初始化第一行和第一列为0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }

        // 根据状态转移方程进行计算
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (w[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
                }
            }
        }

        // 输出最大价值
        System.out.println("背包能够装下的最大价值为：" + dp[n][capacity]);
    }
}

上述代码实现了01背包问题的动态规划解法，其中`w`数组表示物品的重量，`v`数组表示物品的价值，`capacity`表示背包的容量，`n`表示物品的个数。`dp`数组为二维数组，用于存储状态转移方程的结果。具体实现中，我们首先初始化第一行和第一列为0，然后根据状态转移方程进行计算，最后输出背包能够装下的最大价值。