蛮立法解决0/1背包问题Java

0/1背包问题是一个经典的动态规划问题，可以使用Java编写一个程序来解决。

首先，定义一个函数来解决0/1背包问题，该函数接受两个参数：物品重量数组w和物品价值数组v，以及背包容量c：

public static int knapsack(int[] w, int[] v, int c){
    int n = w.length; // 物品数量
    int[][] dp = new int[n+1][c+1]; // dp数组，用于存储每个状态的最优值

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

    // 动态规划，计算每个状态的最优值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            if(w[i-1] <= j){
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 返回最终结果
    return dp[n][c];
}

该函数使用一个二维数组dp来存储每个状态的最优值，其中dp[i][j]表示前i个物品放入容量为j的背包中的最大价值。dp[i][j]的值可以通过以下公式计算得到：

if(w[i-1] <= j){
    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
}else{
    dp[i][j] = dp[i-1][j];
}

其中，w[i-1]表示第i个物品的重量，v[i-1]表示第i个物品的价值。如果第i个物品的重量小于等于当前背包容量j，则可以选择放入该物品，此时dp[i][j]等于不放第i个物品的最大价值dp[i-1][j]和放入第i个物品的最大价值dp[i-1][j-w[i-1]]+v[i-1]的较大值。如果第i个物品的重量大于当前背包容量j，则不能选择放入该物品，此时dp[i][j]等于不放第i个物品的最大价值dp[i-1][j]。

最后，该函数返回dp[n][c]，即前n个物品放入容量为c的背包中的最大价值。

可以在main函数中调用该函数来解决0/1背包问题，例如：

public static void main(String[] args) {
    int[] w = {1, 3, 4, 5}; // 物品重量数组
    int[] v = {1, 4, 5, 7}; // 物品价值数组
    int c = 7; // 背包容量
    int max = knapsack(w, v, c); // 调用knapsack函数求解最大价值
    System.out.println("最大价值为：" + max); // 输出最大价值
}