用动态规划算法求解0-1背包问题。JAVA代码

在动态规划中，我们可以使用二维数组来解决0-1背包问题。这个问题涉及到给定一组物品，每种物品都有一定的价值（value）和重量（weight），目标是在不超过背包容量的前提下，选择一种或多种物品，使得总价值最大。

以下是Java代码的一个简单实现：

public class Knapsack {
    int[] dp; // 动态规划数组，dp[i][w]表示前i个物品，总重量不超过w的最大价值

    public int knapSack(int W, int[] wt, int[] val, int n) {
        dp = new int[n + 1][W + 1];
        
        // 枚举每个物品，如果当前物品的重量小于等于剩余背包容量
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0; // 如果没有物品或背包为空，则价值为0
                } else if (wt[i - 1] <= w) {
                    // 如果当前物品可以放入背包，取最大值：包含当前物品的价值和不包含当前物品的价值
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    // 当前物品无法放入，直接采用不包含当前物品的最优解
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][W]; // 返回装满背包后的最大价值
    }