java写一个01背包问题

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

public class KnapsackProblem {

    /**
     * 01 背包问题求解
     * @param W 背包容量
     * @param wt 物品重量数组
     * @param val 物品价值数组
     * @param n 物品数量
     * @return 最大价值
     */
    public static int knapsack(int W, int[] wt, int[] val, int n) {
        int[][] 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; // 初始化第一行和第一列
                } else if (wt[i-1] <= w) {
                    dp[i][w] = Math.max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]]);
                } else {
                    dp[i][w] = dp[i-1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int W = 50;
        int[] wt = {10, 20, 30};
        int[] val = {60, 100, 120};
        int n = wt.length;
        System.out.println("最大价值：" + knapsack(W, wt, val, n));
    }
}

输出结果：

最大价值：220

其中，`W` 为背包容量，`wt` 为物品重量数组，`val` 为物品价值数组，`n` 为物品数量。函数 `knapsack` 返回最大价值。