golang刷leetcode动态规划（4）分割等和子集（0,1背包问题）

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

1. 每个数组中的元素不会超过 100

2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

问题分析

1，如果所有元素和sum不能被2整除，结果为false

2，如果所有元素和能被2整除，问题转化为从数组中选几个元素使得和为sum/2

3,问题2就是一个背包问题，对于数组中每一个元素，选或者不选，被包容量问sum／2，看最终是否能填满背包

拓展

数组是否可以被k等分＝》sum能不能被k整除＝》数据中选k-1次使得每一次排除上次筛选元素后，本次筛选元素和为sum／k

动态规划：

　　eg：number＝4，capacity＝8

1、原理

　　动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

2、过程

　　a) 把背包问题抽象化（X₁，X_2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），V_i表示第 i 个物品的价值，W_i表示第 i 个物品的体积（重量）；

　　b) 建立模型，即求max(V₁X₁+V₂X₂+…+VnXn)；

　　c) 约束条件，W₁X₁+W₂X₂+…+WnXn<capacity；

　　d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

       e)推关系式，面对当前商品有两种可能性：

　　　　第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

　　　　第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　　　　　　　其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

　　　　由此可以得出递推关系式：

　　　　1) j<w(i)      V(i,j)=V(i-1,j)

　　　　2) j>=w(i)     V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) 

注意：定义V[i][j]的时候，第二维大小应该是容量＋1，v[i][0]=0,解决下标问题

      f)表格填完，最优解即是V(number,capacity)=V(4,8)=10   

      g)由哪些商品组成，故要根据最优解回溯找出解

　          1) V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；

　　　　2) V(i,j)=V(i-1,j-w(i))+v(i)实时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；

　　　　3) 一直遍历到i＝0结束为止，所有解的组成都会找到。

本问题建模：

   1，定义a[i][j] bool ,0<=i<len(nums);0<=j<sum/2+1, 其中a[i][j]表示第i+1个数字，背包容量为j的时候，能否被装满（能否和达到sum/2）

   2,状态转移方程：

   if nums[i]>j{

    a[i][j] =a[i-1][j]  装不下，看下i－1能否装满 

}else {

 a[i][j] =a[i-1][j] ||  a[i][j] =a[i-1][j-nums[i]] 装nums[i]和不装，两种情况任意一种满足就可以装满

 }

3，由于用到了i-1,j-nums[i]所以下标应该递增

4,对于第一个物品i=0，如果j==nums[j],则 a[i][j]=true,可以被装满，其他情况false

5，容量为0的时候，不能被装满a[0:len(nums)][0]=false

5，a[len(nums)－1][sum/2]即为所求结果，如果想知道哪几个数字，就回溯

func canPartition(nums []int) bool {
    sum:=0
    for i:=0;i<len(nums);i++{
        sum+=nums[i]
    } 
    if sum%2!=0{
        return false
    }
    return package01(nums,sum/2)
}


func package01(nums []int, capcity int) bool {
  a := make([][]bool, len(nums))
  for i := 0; i < len(nums); i++ {
    a[i] = make([]bool, capcity+1)
    a[i][0] = false
  }
  for i := 0; i < len(nums); i++ {
    for j := 1; j <= capcity; j++ {
      if j >= nums[i] {
        if i == 0 {
          a[i][j] = j == nums[i]
        } else {
          a[i][j] = a[i-1][j] || a[i-1][j-nums[i]]
        }
      } else {
        if i == 0 {
          a[i][j] = false
        } else {
          a[i][j] = a[i-1][j]
        }
      }
    }
  }
  return a[len(nums)-1][capcity]
}