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

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

【0-1】背包问题

1. 背包问题

1.1 题目描述

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

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 的价值.

代码实现如下:

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

2. leetcode 416 Partition Equal Subset Sum 及题解

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

2.1 题目描述

Given a non-empty array containing

Note:

Example 1:

<code>Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]./<code>

Example 2:

<code>Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets./<code>

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

2.2 题目求解

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

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

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

dp[i] = dp[i-j]

以下是代码实现:

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

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/背包问题]