01背包 java代码

以下是一个简单的01背包问题的Java代码实现：

public class Main {
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 物品重量
        int[] values = {3, 4, 5, 6}; // 物品价值
        int capacity = 8; // 背包容量
        int n = weights.length; // 物品数量

        int[][] dp = new int[n + 1][capacity + 1]; // dp数组

        // 初始化dp数组
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= capacity; j++) {
                dp[i][j] = 0;
            }
        }

        // 动态规划
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        // 输出结果
        System.out.println("最大价值为：" + dp[n][capacity]);
    }
}

其中，`weights`数组和`values`数组分别表示物品的重量和价值，`capacity`表示背包的容量，`n`表示物品的数量。`dp`数组表示动态规划表，`dp[i][j]`表示在前`i`个物品中选择不超过`j`的重量所能获得的最大价值。

在动态规划过程中，对于每个物品，如果其重量超过了当前背包的容量，则无法放入背包，此时`dp[i][j]`等于上一个物品的最优解`dp[i-1][j]`；否则，可以选择放入或不放入该物品，取两者之间的最大值作为`dp[i][j]`的值。最终，`dp[n][capacity]`即为所求的最大价值。