01背包问题java代码

01背包问题是一个经典的动态规划问题，它的主要思想是：将问题分解成子问题，通过保存子问题的最优解来推导出原问题的最优解。

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

public class KnapsackProblem {
    public static int knapsack(int[] w, int[] v, int c) {
        int n = w.length;
        int[][] dp = new int[n][c + 1];
        for (int j = 0; j <= c; j++) {
            dp[j] = j >= w ? v : 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= w[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        return dp[n - 1][c];
    }

    public static void main(String[] args) {
        int[] w = {2, 3, 4, 5};
        int[] v = {3, 4, 5, 6};
        int c = 8;
        System.out.println(knapsack(w, v, c)); // 输出：11
    }
}

在以上代码中，我们通过二维数组dp来保存每个子问题的最优解，其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。初始化时，我们将第一个物品放入背包中，并记录每个容量所能获得的最大价值；接着，我们从第二个物品开始遍历，对于每个物品和容量，我们分两种情况考虑：放或不放。如果不放，则背包中的物品和价值保持不变，即dp[i][j] = dp[i-1][j]；如果放，则需要考虑新加入物品所占用的容量和价值，即dp[i][j] = dp[i-1][j-w[i]] + v[i]。最终，我们返回dp[n-1][c]，即前n个物品放入容量为c的背包中所能获得的最大价值。