目录

零、背包问题

一、01背包

二、分割等和子集

三、目标和

四、最后一块石头的重量II

---

零、背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量（或体积）内，我们如何选择，才能使得物品的总价格最高。

其中的限制条件有：物品价值，背包容量大小，背包是要求必装满还是不必装满，每种物品的数量。

一、01背包

01背包可以描述为：有n件物品和一个最多能背体积为 v 的背包。第 i 件物品的体积是 v[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

在01背包问题中，对于每件物品，只有两种状态：选或者不选。

题目

01背包

题目解析 

第一问的所有情况就是上图蓝色方框的内容， 第二问的所有情况就是上图红色方框的内容。

解决第一问 

第一步：确定状态表示

dp[i][j]：表示从前 i 个物品中挑选，总体积不超过 j 的所有选法中，能挑选出来的物品价值最大值。

第二步：推出状态转移方程

前面我们已经说明了，01背包中的每件物品只有一种，所以对于每件物品来说，只有选或者不选两种状态。根据最后一步的状况，分情况讨论，即要么选择 i 号物品，要么不选 i 号物品。

如果要选 i 物品，在所有选法中，最后一个被选择的一定是 i 物品，那么总价值要加上w[i]表示 i 号物品的价值。

接下来只要知道选到  i - 1 号物品时的最大价值就行了，但是此时的体积就不再是 j 了。因为挑到 i 号物品的时候总体积要求不超过 j ，那选了 i 号物品，然后从1 ~ i - 1物品选，要剩下一点体积能让我挑选 i 号物品。

所以体积需要剩余 j - v[i]。也就是说选了 i 号物品，接下来去1 ~ i - 1物品选总体积不能超过j - v[i]。

并且，前一个状态的最大价值，正好在 dp[i-1][j-v[i]]里存着。

注：j - v[i] 不一定存在。比如说挑选到 i 号物品的时候总体积要求不超过3，但是第 i 号物品的体积是6，这要求背包剩余空间是-3，是一个负数，那怎么也装不下。那选 i 号物品这种情况就相当于不存在。如果想选 i 号物品这种情况存在，那 j - v[i] >= 0。 

第三步：初始化dp表

为了方便，我们规定物品的编号是从1开始的。所以为了填写下标关系一一对应，我们给dp表多加一行和一列。

第一行 i 等于0，表示从0号物品中选，但是我们规定物品编号是从1开始的。第一行表示没有物品，如果没有物品，想凑成容量不超过 j 根本不可能做到，所以第一行值都为0。

第一列表示容量不超过0，那么不选的话容量就不会超过0了。

最后的返回值就是dp[n][V]。 

解决第二问 

第一步：确定状态表示

dp[i][j]： 表示从前 i 个物品中挑选，总体积恰好为 j 的所有选法中，能挑选出来的物品价值最大值。

第二步：推出状态转移方程

该状态转移方程和第一问的一模一样，但是需要注意一些限制条件。

dp[i][j]表示从前 i 个物品中挑选，总体积恰好为 j 的所有选法中，能挑选出来的物品价值最大值。该状态表示要求，当我们选到第 i 个物品的时候，体积要恰好为 j。但是我们不一定就能选到使其体积恰好为j。那就说明这种状态是不存在的。

为了处理这种情况，我们规定，dp[i][j] = -1 表示情况不存在。

所以我们在用每一个状态之前都要判断状态存不存在，然后才能使用。比如选 i 物品，要判断 dp[i-1][j-v[i]] != -1，然后再使用这个状态。

第三步：初始化dp表

第一列（下标从0开始）表示使体积恰好为0，什么也不选体积就恰好是0，价值也是0。

第一行（下标从1开始）表示没有物品，但是想凑成体积恰好等于 j 的情况，这种状态是根本不存在的，所以值为-1。

解题代码：

#include <algorithm>
#include <iostream>
#include <vector>using namespace std;int main()
{int n, V;cin >> n >> V;vector<int> v(n+1);vector<int> w(n+1);for(int i = 1; i <= n; i++)cin >> v[i] >> w[i];vector<vector<int>> dp1(n+1, vector<int>(V+1));for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp1[i][j] = dp1[i-1][j];if(j-v[i] >= 0)dp1[i][j] = max(dp1[i][j], dp1[i-1][j-v[i]] + w[i]);}}vector<vector<int>> dp2(n+1, vector<int>(V+1));for(int i = 1; i <= V; i++)dp2[0][i] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j <= V; j++){dp2[i][j] = dp2[i-1][j];if(j-v[i] >= 0 && dp2[i-1][j-v[i]] != -1)dp2[i][j] = max(dp2[i][j], dp2[i-1][j-v[i]] + w[i]);}}cout << dp1[n][V] << endl;cout << (dp2[n][V] == -1 ? 0 : dp2[n][V]) << endl;return 0;
}

 

---

二、分割等和子集

分割等和子集

题目解析 

题目要求将数组分成元素和相等的两个部分，而数组的元素总和是固定的，那就说明这两个部分的值都是数组元素总和的一半。

那么，这个问题就转化成了，从数组中选取一些元素，看能不能使选出来的元素和恰好为数组总和的一半。 每个元素只有两种状态，选或者不选，并且每个元素是只能选一次的。这不就是01背包问题吗。下面我们就用解决01背包问题的方法来解决这道题。

解题

第一步：确定状态表示

dp[i][j]：表示从数组的前 i 个元素中挑选元素，能不能使其总和恰好为 j，能就是true，不能就是false。

第二步：推出状态转移方程

第三步：初始化dp表

第一列（下标从0开始）表示使元素和恰好为0，什么也不选和就恰好是0，所以是true。

第一行（下标从1开始）表示没有元素，但是想凑成和恰好等于 j 的情况，这种状态是根本不存在的，所以值为false。

最后的返回值就是dp[m][sum/2]。 

解题代码：

class Solution 
{
public:bool canPartition(vector<int>& nums) {int m = nums.size();int sum = 0;for(auto x : nums)sum += x;if(sum % 2 != 0)return false;int target = sum / 2;vector<vector<bool>> dp(m+1, vector<bool>(target+1));for(int i = 0; i <= m; i++)dp[i][0] = true;for(int i = 1; i <= m; i++){for(int j = 1; j <= target; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];}}return dp[m][target];}
};

---

三、目标和

目标和

题目解析

题目要求给数组的元素前面添上正号或者负号，那就相当于把一个元素变成正数或者负数。

所以，我们可以将元素分成两个部分，一部分是正数，一部分是负数。那么我们可以推出如下的结果。

推出的结果是 a = （target + sum）/ 2。

于是，问题就转化成了：只要在整个数组里挑选一些数让这些数的和等于a即可，然后问一共有多少种挑法。  

数组的每个数都有选或者不选两种状态。我们的目的是让选择的数的和等于a。这就是01背包问题里面把背包恰好装满的问题。

解题 

第一步：确定状态表示

dp[i][j]：表示从数组的前 i 个元素中选，使总和正好等于 j，一共有多少种选法。

第二步：推出状态转移方程

第三步：初始化dp表

第一行表示数组没有元素，如果数组里面没有元素，只要不选，就可以凑出和为0的情况，第一个位置为1，但是无法凑出和为1、2…的情况。所以第一行剩下都为0。

我们初始化的目的是为了在填表的时候不会发生越界访问。对于第一列剩下的位置，表示和恰好为0。因为数组元素可能是0，选 i 位置元素的时候，会判断是否 j >= nums[i]，第一列的 j 都是0，要符合判断的话，只能是nums[i] == 0，nums[i] > 0 的话根本就不会进入 “选i位置元素” 的情况，所以绝对不会越界访问。

所以第一列剩下的位置可以放在填写dp表时进行填写。

解题代码：

class Solution 
{
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(auto x : nums)sum += x;int m = nums.size();int num = (target + sum) / 2;if(num < 0 || (sum + target) % 2)return 0;vector<vector<int>> dp(m+1, vector<int>(num+1));dp[0][0] = 1;for(int i = 1; i <= m; i++){for(int j = 0; j <= num; j++){dp[i][j] = dp[i-1][j];if(j >= nums[i-1])dp[i][j] += dp[i-1][j-nums[i-1]];}}return dp[m][num];}
};

 

---

四、最后一块石头的重量II

最后一块石头的重量II

题目解析

这道题如果直接用动态规划去做是很难的。状态表示定义不出来。所以我们先分析这道题看能不能把这道题转换一下。 

我们先模拟一下选择过程：

最后，数组中剩下的元素就是我们想要的结果。

我们发现，这和上一道题目标和好像有些像， 最后的结果也是在元素前面添上正号或者负号而得到的，那就相当于把一个元素变成正数或者负数。这样数组就会只剩下一个元素了。

这道题是让我们求剩下的石头的最小重量，所以这道题我们就可以转换成：在数组中选择一些数，让这些数的和尽可能的接近 sum / 2。只要能求出a就能求出b，然后让它俩相减就可以了。

数组里面所有的数都面临选或者不选两种情况，并且每个位置的元素只有一个，这就是典型的01背包问题。

解题 

第一步：确定状态表示

dp[i][j]：表示从前 i 个数中选，使其总和不超过 j，此时的最大和。

第二步：推出状态转移方程

第三步：初始化dp表

第一列不用初始化。

第一行表示数组为0的情况，也就是没有石头，要想凑成总和不超过j，当 j 是 0 的时候不选就可以了此时最大和为0。但当 j 是1、2…，根本凑不成，此时最大和还是0。

解题代码：

class Solution 
{
public:int lastStoneWeightII(vector<int>& stones) {int m = stones.size();int sum = 0;for(auto x : stones)sum += x;int target = sum / 2;vector<vector<int>> dp(m+1, vector<int>(target+1));for(int i = 1; i <= m; i++){for(int j = 0; j <= target; j++){dp[i][j] = dp[i-1][j];if(j >= stones[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-stones[i-1]] + stones[i-1]);}}return sum - 2 * dp[m][target];}
};