java求解简单的0/1背包问题

在Java中，解决0/1背包问题通常会采用动态规划算法。0/1背包问题是一个经典的组合优化问题，给定一组物品，每种物品都有一个价值和重量，目标是在不超过背包容量的前提下，选择一种物品组合使得总价值最大。

以下是使用动态规划求解0/1背包问题的基本步骤：

1. 定义状态：令`dp[i][w]`表示前i件物品放入容量为w的背包能获得的最大价值。

2. 状态转移方程：对于第i件物品，有两种选择：取或不取。如果取，则`dp[i][w] = dp[i-1][w] + val[i]`；如果不取，则`dp[i][w] = dp[i-1][w]`。取的时候需要判断当前物品的重量`weight[i]`是否小于等于剩余的背包容量`w`。

3. 初始条件：`dp[0][w] = 0`，表示没有物品的情况下背包价值为0；当物品数量为0时，无论包多重，价值都是0，即`dp[i][0] = 0`。

4. 最终结果：在所有状态计算完毕后，`dp[n][W]`就是所求的最大值，其中n是物品的数量，W是背包的容量。

int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[][] dp = new int[n+1][W+1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) { // 可以装下
                dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]);
            } else { // 装不下
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    return dp[n][W];
}