javaScript实现动态规划(Dynamic Programming)01背包问题

function knapsack(weight, values, maxWeight) {
    let n = weight.length;
    let dp = new Array(n).fill(0).map(() => new Array(maxWeight + 1).fill(0));
 
    for (let i = 0; i < n; i++) {
        if (weight[i] <= maxWeight) {
            dp[i][weight[i]] = values[i];
        }
    }
 
    for (let i = 1; i < n; i++) {
        for (let j = 1; j <= maxWeight; j++) {
            if (weight[i] <= j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + values[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    return dp[n - 1][maxWeight];
}
 
// 示例使用
let weight = [2, 1, 3]; // 物品的重量数组
let values = [4, 2, 5]; // 物品的价值数组
let maxWeight = 4; // 背包的最大重量
 
let result = knapsack(weight, values, maxWeight);
console.log(result); // 输出背包可以容纳的最大价值

这段代码实现了01背包问题，并使用了一个二维数组dp来记录状态，最后返回了最大价值。这是一个经典的动态规划问题，适用于求解类似的背包问题。