function knapSack(W, wt, val, n) {
    // n 是物品数量
    // 创建一个 (n+1) x (W+1) 的二维数组，初始化为 0
    // dp[i][w] 表示前 i 个物品在容量 w 下的最大价值
    const dp = new Array(n + 1).fill(0).map(() => new Array(W +1).fill(0));

    // 遍历所有物品 (从 1 开始，因为 0 代表没有物品)
    for (let i = 1; i <= n; i++) {
        // 遍历所有可能的容量 (从 1 开始，0 容量价值为 0)
        for (let w = 1; w <= W; w++) {
            
            // 当前物品的重量和价值 (数组是 0-indexed，所以用 i-1)
            const weight = wt[i - 1];
            const value = val[i - 1];

            if (weight <= w) {
                // 装得下：取“不装”和“装”两者的最大值
                dp[i][w] = Math.max(
                    dp[i - 1][w],                          // 不装
                    dp[i - 1][w - weight] + value          // 装
                );
            } else {
                // 装不下：只能继承前 i-1 个物品的结果
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 返回最终结果：n 个物品在容量 W 下的最大价值
    return dp[n][W];
}

// 测试用例
const val = [60, 100, 120]; // 物品价值
const wt = [10, 20, 30];    // 物品重量
const W = 50;               // 背包容量
const n = val.length;

console.log("最大价值:", knapSack(W, wt, val, n)); // 输出: 220 (选物品2和物品3)