编辑代码

public class Knapsack {  
    public static int maxValue(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 j = 1; j <= W; j++) {  
                if (weights[i - 1] <= j) {  
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);  
                } else {  
                    dp[i][j] = dp[i - 1][j];  
                }  
            }  
        }  
        return dp[n][W];  
    }  

     public static void main(String[] args) {  
        // 物品数量n=3，背包承重限制W=5，物品重量weights=[2, 3, 4]，物品价值values=[3, 4, 5]，最大价值应为7。
        int[] weights1 = {2, 3, 4};  
        int[] values1 = {3, 4, 5};  
        int W1 = 5;  
        int maxValue1 = Knapsack.maxValue(weights1, values1, W1);  
        System.out.println("测试用例1：Max value: " + maxValue1);  
  
        // 物品数量n=4，背包承重限制W=7，物品重量weights=[2, 3, 4, 5]，物品价值values=[3, 4, 5, 6]，最大价值应为12。 
        int[] weights2 = {2, 3, 4, 5};  
        int[] values2 = {3, 4, 5, 6};  
        int W2 = 7;  
        int maxValue2 = Knapsack.maxValue(weights2, values2, W2);  
        System.out.println("测试用例2：Max value: " + maxValue2);  
  
        // 物品数量n=5，背包承重限制W=10，物品重量weights=[2, 3, 4, 5, 6]，物品价值values=[3, 4, 5, 6, 7]，最大价值应为15。  
        int[] weights3 = {2, 3, 4, 5, 6};  
        int[] values3 = {3, 4, 5, 6, 7};  
        int W3 = 10;  
        int maxValue3 = Knapsack.maxValue(weights3, values3, W3);  
        System.out.println("测试用例3：Max value: " + maxValue3);  
  
        // 物品数量n=6，背包承重限制W=15，物品重量weights=[2, 3, 4, 5, 6, 7]，物品价值values=[3, 4, 5, 6, 7, 8]，最大价值应为18。  
        int[] weights4 = {2, 3, 4, 5, 6, 7};  
        int[] values4 = {3, 4, 5, 6, 7, 8};  
        int W4 = 15;  
        int maxValue4 = Knapsack.maxValue(weights4, values4, W4);  
        System.out.println("测试用例4：Max value: " + maxValue4);  
    }  

}