一个典型的背包问题

问题描述

问题链接

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  • Each of the array element will not exceed 100.
  • The array size will not exceed 200.

Example 1:


Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:


Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

问题分析

首先可以确定这是一个背包问题,最优结果是从n件物品中取出的物品恰好和剩余的物品价值相等,那么背包的容量是多少?为了保证取出来的和剩下的相等,背包的容量必然是sum / 2,所以判断的时候先求和判断是不是偶数,不是偶数肯定没办法保证取出的和剩下的下等,其次这个背包必须恰好装满。

代码


/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canPartition = (nums) => {
  const sum = nums.reduce((prev, curr) => prev + curr, 0)
  if(sum % 2 !== 0) {
    return false
  }
  const size = sum / 2
  const dp = Array(size + 1).fill(-200000)
  dp[0] = 0
  for(let i = 0; i < nums.length; i++) {
    for(let j = size; j >= nums[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
    }
  }
  return dp[size] > 0
}