背包问题是软件工程师面试中常问的问题，它被变形成许多问题用于考察面试者的思维能力. 背包问题的思路主要是将复杂的问题划分为子问题，先依次求解子问题，最终再求得原问题. 本文探究的背包问题为 0-1 背包问题，并解析 leetcode 416.

【0-1】背包问题

1. 背包问题

1.1 题目描述

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

1.2 解题思路

这个问题最简答的思路就是穷举法, 另一个方法是动态规划, 依次求解子问题.

穷举法: 最基础的思路，可以尝试各种商品的组合，然后选出背包内价值最大的组合. 通过这种思路，每个物品都有放入背包、不放入背包两种选项，总的组合数量是 2^n . 时间复杂度是 o(2^n). 这样的指数型时间复杂度显然在工程上是不可取的.

动态规划: 这个题目可以考虑使用动态规划法，先解决局部的子问题，再解决最终的问题. 动态规划问题的核心是找到动态规划方程式，用于将问题划分成子问题. 下面是分析思路.

容量为 v 的背包，可以划分为两个容量为 v1 + v2 = v 的背包组合. 这两个背包的组合的价值和可能是容量为 v 的背包最大价值的潜在答案之一，v1、v2 依次分解成小容量背包，就可以反向递推容量为 v 的背包问题的解了. 那么如何将容量为 v 的背包进行划分呢？

可以考虑依次将第 i 个( i 从 1 到 n 遍历)物品拿出来，它的体积是 ci . 此时选择是否将物品放入背包. 那么就有两种可能， 放入该物品和不放入该物品. 放入该物品的话，需要确保背包容量足够，不放入该物品，则当前的背包最大价值与第 i-1 个物品取出时的情况相同.

比较这两种情况得到的价值，若背包中放入物品价值更大且容量满足，则第 i 个物品时，背包的最优解是放入物品 i. 否则第 i 个物品取出的最优解等同于第 i-1 个物品取出的情况.

在计算放入第 i 个物品时背包的最大价值时，需要知道容量为背包容量为 v - ci 的子问题背包的最大价值.

这个问题的划分思路是，计算放入第 i 个物品时，依次计算背包容量为 1～v 时的最优解. 最终计算到第 n 个物品时，容量为 v 的最优解就是原题目的最终解. 动态规划的方程式为如下:

上述公式中 dp[i][j] 代表前 i 个物品, 背包容量为 j 时背包问题的最有解, 其中 0 <= i < n, 0 <= j <= v. ci 为物品 i 的体积，v[i] 为物品 i 的价值.

代码实现如下:

// 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]
}

2. leetcode 416 Partition Equal Subset Sum 及题解

背包问题作为经典问题，它的解题思路被应用在许多问题上. 是面试中常问的问题. 其中 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]
}

3. END

3.1 其它

0-1 背包问题是背包问题的其中一种，背包问题可以划分为三类，包括: 0-1 背包问题、完全背包问题、多重背包问题. 它们是动态规划的经典问题.

背包可以出现在各领域的现实世界的决策过程，如资产证券化、投资组合、选择投资等. 背包问题除了在面试中常常出现，也是是十分值得去探索的问题，它已经被研究超过了 1 个世纪.

3.2 参考文献

1. 0-1 背包问题 [https://www.jianshu.com/p/a66d5ce49df5]

2. partition equal subset sum [https://leetcode.com/problems/partition-equal-subset-sum/]

3.背包问题 [https://baike.baidu.com/item/背包问题]