fyhub's blog

Appearance

5.分割等和子集 ​

思路 ​

  • 背包的体积为 sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如何正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

题解 ​

::: code-tabs#js

@tab 二维数组解法

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((a, b) => a + b)
    if (sum % 2 !== 0) return false
    const num = sum / 2
    const dp = new Array(nums.length).fill().map(() => new Array(num + 1).fill(0))
    for (let i = nums[0];i <= num;i++) {
        dp[0][i] = nums[0];
    }
    for (let i = 1;i < nums.length;i++) {
        for (let j = 0;j <= num;j++) {
            // 背包容量没有物品大
            if (j < nums[i]) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - nums[i]] + nums[i], dp[i - 1][j])
            }
        }
    }
    return dp[nums.length - 1][num] === num
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((a, b) => a + b)
    if (sum % 2 !== 0) return false
    const num = sum / 2
    const dp = new Array(nums.length).fill().map(() => new Array(num + 1).fill(0))
    for (let i = nums[0];i <= num;i++) {
        dp[0][i] = nums[0];
    }
    for (let i = 1;i < nums.length;i++) {
        for (let j = 0;j <= num;j++) {
            // 背包容量没有物品大
            if (j < nums[i]) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - nums[i]] + nums[i], dp[i - 1][j])
            }
        }
    }
    return dp[nums.length - 1][num] === num
};

@tab 滚动数组解法

js
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const sum = nums.reduce((a, b) => a + b);
  // 如果不是2的整数 直接返回false
  if (sum & 1) return false;

  // 背包容量最大为数组总和的一半
  const target = sum / 2;
  const dp = new Array(target + 1).fill(0);

  // 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // 倒序遍历背包容量
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
    }
  }
  return dp[target] === target;
};
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const sum = nums.reduce((a, b) => a + b);
  // 如果不是2的整数 直接返回false
  if (sum & 1) return false;

  // 背包容量最大为数组总和的一半
  const target = sum / 2;
  const dp = new Array(target + 1).fill(0);

  // 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // 倒序遍历背包容量
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
    }
  }
  return dp[target] === target;
};

:::