0-1 背包问题及 leetcode 416 题解

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有n件可用，每件体积是c，
价值是 w . 求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且
价值总和最大.

// golang 实现
//动态规划
func backpack(capacities []int, values []int, capacity int) int {
    dp := make([][]int, len(values)) 
    
    for i := 0; i < len(values); i++ {
        dp[i] = make([]int, capacity+1)
    }
    
    // 只有一个物品时，背包问题的 dp[0] 解
    for i := capacities[0]; i < capacity; i++ {
       dp[0][i] = values[0]
    }
       
    for i := 1 ; i < len(values); i++ {
    for j := 0;j <= capacity; j++ {
            if j < capacities[i] || dp[i-1][j] >= values[i] + dp[i][j - capacities[i]] {
               dp[i][j] = dp[i-1][j]
            }else {
                dp[i][j] = values[i] + dp[i][j - capacities[i]]
            }
    }
  }
  return dp[len(values)-1][capacity]
}

背包问题作为经典问题，它的解题思路被应用在许多问题上. 是面试中常问的问题. 其中 Leetcode 416 的解题思路就是背包问题. 实际上，leetcode 416 是更简单的背包问题.

2.1 题目描述

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:

1. Each of the array element will not exceed 100.

2. 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.

题目大意是给予一个正整数数组，判断是否可以将数组分为两个子数组，且两个子数组的和是相等的.

2.2  题目求解

这道题和背包问题一样，可以采用穷举法，列出所有的组合，但是时间复杂度太高，工程上是不可行的. 另一种方法也是动态规划，可以将其划分为子问题，先求子问题，在逐步求解原问题.  

实际上，这道题可以通过将背包容量设置为 sum/2 ，每个数的大小作为物品的体积，这题的最优解不需要考虑物品的价值，而是能否将背包填满. 事实上，它比背包问题更简单.  它只有一个体积，子问题即容量为 0 ~ sum/2 的背包是否能够被前 i 个物品的组合正好填满.  

我们设 dp[i] 为容量为 i 的背包能否被前 j 个物品的组合正好填满, nums[j] 为物品的体积. 则动态规划方程式为:

 dp[i] = dp[i-j]

以下是代码实现: 

// golang 实现
func canPartition(nums []int) bool {
  var sum int
  for _, num := range nums {
    sum += num
  }


  // sum/2 有小数，nums 都为正数，显然不可以
  if sum % 2 == 1 {
    return false
  }


  sum = sum  2  // 目标 target
  dp := make([]bool, sum+1)
  dp[0] = true
  for _, v := range nums {
    // 加入体积为 v 的数后，重新判断容量为 v ~ sum 的背包是否能被填满
    for j := sum; j > 0; j-- {
      if j >= v && dp[j-v] {
        dp[j] = true
      }
    }
  }
  return dp[sum]
}