动态规划

字数

1414 字

阅读时间

7 分钟

背包问题

0-1 背包问题：内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次（每层的滚动数组从右往左滚动，利用的是左上方的数据，而左上方的数据中还没有放入物品，所以保证了每个物品仅仅被添加一次）。

完全背包问题：物品可以添加多次，所以要从小到大去遍历。

0-1 背包问题

0-1 背包问题中，每个物品只能选择一次。

二维 dp 数组解法

/**
 * 解决 0-1 背包问题
 * @param {number[]} weight 物品的重量数组
 * @param {number[]} value 物品的价值数组
 * @param {number} size 背包的容量
 * @returns {number} 能放入背包的最大价值
 */
function testWeightBagProblem(weight, value, size) {
    const len = weight.length;
    // dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值
    const dp = Array(len).fill(0).map(() => Array(size + 1).fill(0));

    // 初始化：当只考虑第一个物品时
    // 如果背包容量 j 大于等于第一个物品的重量，则可以放入第一个物品
    for (let j = weight[0]; j <= size; j++) {
        dp[0][j] = value[0];
    }

    // 遍历物品
    for (let i = 1; i < len; i++) {
        // 遍历背包容量
        for (let j = 0; j <= size; j++) {
            // 如果当前背包容量 j 小于第 i 个物品的重量，则无法放入第 i 个物品
            // 此时的最大价值等于不放入第 i 个物品时的最大价值
            if (j < weight[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // 如果可以放入第 i 个物品，则比较两种情况：
                // 1. 不放入第 i 个物品：dp[i - 1][j]
                // 2. 放入第 i 个物品：dp[i - 1][j - weight[i]] + value[i]
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }
        }
    }

    console.table(dp);

    return dp[len - 1][size];
}

滚动数组（一维 dp 数组）解法

/**
 * 解决 0-1 背包问题（滚动数组优化）
 * @param {number[]} weight 物品的重量数组
 * @param {number[]} value 物品的价值数组
 * @param {number} size 背包的容量
 * @returns {number} 能放入背包的最大价值
 */
function testWeightBagProblem(weight, value, size) {
    const len = weight.length;
    // dp[j] 表示背包容量为 j 时的最大价值
    const dp = Array(size + 1).fill(0);

    // 遍历物品
    for (let i = 0; i < len; i++) {
        // 遍历背包容量，从大到小，确保每个物品只被选择一次
        for (let j = size; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], value[i] + dp[j - weight[i]]);
        }
    }
    return dp[size];
}

完全背包问题

完全背包问题中，每个物品可以被选择多次。

• 物品在 for 循环外层，背包容量在内层，通常得到的是组合数。
• 背包容量在 for 循环外层，物品在内层，通常得到的是排列数。

// 先遍历物品，再遍历背包容量（求组合数）
function test_completePack1() {
    let weight = [1, 3, 5];
    let value = [15, 20, 30];
    let bagWeight = 4; // 背包容量
    let dp = new Array(bagWeight + 1).fill(0);

    for (let i = 0; i < weight.length; i++) { // 遍历物品
        for (let j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量，从小到大
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    console.log(dp[bagWeight]);
}

// 先遍历背包容量，再遍历物品（求排列数）
function test_completePack2() {
    let weight = [1, 3, 5];
    let value = [15, 20, 30];
    let bagWeight = 4; // 背包容量
    let dp = new Array(bagWeight + 1).fill(0);

    for (let j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for (let i = 0; i < weight.length; i++) { // 遍历物品
            if (j >= weight[i]) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }
    console.log(dp[bagWeight]);
}

使用二维数组解决排列问题

此示例代码似乎是解决组合总和问题，而非典型的完全背包排列问题。dp[i][j] 表示由前 i 个数组成和为 j 的方案数。

// dp[i][j] 表示由前 i 个数组成和为 j 的方案数
// 此处代码可能用于解决组合总和问题，而非典型的完全背包排列问题
function combinationSum(nums, target) {
    let len = nums.length;
    // dp[i][j] 表示使用前 i 个物品，凑成和为 j 的方案数
    let dp = new Array(len + 1).fill(0).map(() => new Array(target + 1).fill(0));

    // 初始化：凑成和为 0 的方案只有一种（不选择任何物品）
    for (let i = 0; i <= len; i++) {
        dp[i][0] = 1;
    }

    // 对 nums 进行排序，以确保后续 dp[i][j - nums[k]] 的计算逻辑正确
    // 并且在处理重复元素时，可以更好地进行剪枝或去重
    nums.sort((a, b) => a - b);

    for (let j = 1; j <= target; j++) { // 遍历目标和
        for (let i = 1; i <= len; i++) { // 遍历物品
            // 如果当前物品 nums[i-1] 大于目标和 j，则不能选择当前物品
            dp[i][j] = dp[i - 1][j]; // 继承不选择当前物品的方案数
            
            // 如果可以选择当前物品 nums[i-1]
            if (nums[i - 1] <= j) {
                // 遍历所有可能的选择次数（或组合方式）
                // 注意：这里的 k 循环可能导致重复计算或逻辑错误，具体取决于问题定义
                // 对于组合总和问题，通常是 dp[i][j] = dp[i-1][j] + dp[i][j - nums[i-1]]
                // 这里的实现更像是求排列数，但 k 的范围和 dp 状态定义需要更精确
                for (let k = 0; k < i; k++) { // 这里的 k 循环可能需要根据具体问题调整
                    if (j - nums[k] >= 0) { // 确保索引有效
                        dp[i][j] += dp[i][j - nums[k]];
                    }
                }
            }
        }
    }
    return dp[len][target];
}


<NolebaseGitContributors />


<NolebaseGitChangelog />