动态规划
01背包
01背包 二维数组
有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每 件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。
暴力解法 ：很多题目上来，应该先看看暴力解法，暴力解法代表了最顺畅的思路，在此基础上才延伸出其他巧妙地解法。本题每件物品有两种状态：选、不选，那么可以通过回溯法，列出所有可能的组合，计算出价值，在回溯的过程中，用一个maxValue存储最大值；也可以通过计算当前重量，一旦超过背包容量就剪枝；但时间复杂度比较高，为O(2n)。
动态规划 ：二维dp数组
-
确定
dp数组以及下标含义；dp[i][j]表示从下标[0,i]任意取，放进容量为j的背包里，得到的最大价值 -
确定递推公式；
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]+value[i]])=max(不选物品i的最大价值，选物品i的最大价值) -
dp初始化；0 1 2 3 4 0 0 dp[0][j]：只能选择标号为0的物品，无疑所有的价值都是value[0]for(int j=bagWeight;j>=weight[0];--j) { dp[0][j]=dp[0][j-weight[0]]+value[0]; }//这个地方，为什么不是直接赋值成：dp[0][j]=value[0];?dp[i][0]：背包容量为0，无疑所有的价值都为0 -
确定遍历的顺序；
一般为了理解题目意思，先遍历物品，再遍历背包，但也可以先遍历背包再遍历物品
for(int i=1;i<weight.size();++i) { for(int j=0;j<=bagWeight;++j) { if(j<weight[i]) dp[i][j]=dp[i-1][j]; //最大价值=不选物品i的最大价值 else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]+value[i]]); } }
举个栗子
#include<bits/stdc++.h>
using namespace std;
class Solution{
public:
int maxValue(int bagWeight,vector<int>& w,vector<int>& v)
{
vector<vector<int>> dp(w.size()+1,vector<int>(bagWeight+1,0));
for(int j=bagWeight;j>=w[0];--j)//只能选物品0的价值
dp[0][j]=dp[0][j-1]+v[0];//为什么不这样写 dp[0][j]=v[0];
for(int i=1;i<w.size();++i)//先遍历物品
{
for(int j=0;j<=bagWeight;++j)//再遍历背包
{
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
for(int i=0;i<w.size()+1;++i)
{
for(int j=0;j<bagWeight+1;++j)
{
cout <<dp[i][j]<<" ";
}
cout<<endl;
}
return dp[w.size()-1][bagWeight];
}
};
int main()
{
Solution A;
vector<int> weight = {
1, 3, 4};
vector<int> value = {
15, 20, 30};
int bagWeight = 4;
int ans=A.maxValue(bagWeight,weight,value);
return 0;
}
打印结果：
0 15 15 15 15
0 15 15 20 35
0 15 15 20 35
0 0 0 0 0
不太明白，最后一层的意义是什么，为什么定义数组的时候，物品需要多一层，但在实际运用中，有没有用到？
01背包 滚动数组
上述的dp数组是二维的，实际中可以使用一维数组（滚动数组）来代替，可以减少空间复杂度；
dp[i] ：容量为i的背包可以装的最大价值；
#include<bits/stdc++.h>
using namespace std;
class Solution{
public:
int maxValue(int bagWeight,vector<int>& w,vector<int>& v)
{
//初始化，当物品的价值有负数的时候，初始值应该为一个最小数，例如int对应 -2^32
vector<int> dp(bagWeight+1,0);
//遍历
for(int i=0;i<w.size();++i)//先遍历物品
{
for(int j=bagWeight;j>=w[i];--j)//再遍历背包
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
//结果
return dp[bagWeight];
}
};
int main()
{
Solution A;
vector<int> weight = {
1, 3, 4};
vector<int> value = {
15, 20, 30};
int bagWeight = 4;
int ans=A.maxValue(bagWeight,weight,value);
return 0;
}
需要注意的几处地方：
- 初始化：当物品的价值有负数的时候，dp数组的初始值不能直接设为0，而应该是一个最小的负数；
- 遍历的方向：使用滚动数组，只能先遍历物品，再遍历容量，并且容量需要从大到小遍历，防止物品价值重复添加
问：为什么必须先遍历物品，再遍历背包？
**答：**反过来，每次背包里面只装了一个物品
问：为什么背包遍历是从大到小？
**答：**因为，从小到大，会出现物品价值重复计算的问题
416 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
暴力回溯：每个元素有两种选择：选或者不选；当最终和满足条件的时候，就返回true，否则返回false；
动态规划：将题目转换为01背包问题 ：背包的最大容量是sum/2，物品的价值和重量都是nums[i]，dp[i]表示容量为i的背包装的数字最大和
区分01背包和完全背包：物品是否可以重复放入。可重复放入是完全背包，不可重复放入是01背包
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int sum=0;
for(auto i:nums) sum+=i;
if(sum&0x01) return false;
int target=sum/2;
vector<int> dp(target+1,0);
for(int i=0;i<nums.size();++i)
{
for(int j=target;j>=nums[i];--j)
{
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[target]==target;
}
};
什么情况下会出现返回false？
例如 ：nums={8,8,4}
0 0 0 0 0 0 0 0 8 8 8
0 0 0 0 0 0 0 0 8 8 8
0 0 0 0 4 4 4 4 8 8 8
dp[2][10] ：表示从下标[0,2]里面选，背包容量为10，最大可以装的数字和为8，此时，就是返回false的情况；
494 目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路 ：如何转换为01背包问题呢？将数组分为两部分，left+right=sum;left-right=target,那么
left=(sum+target)/2; 背包容量就是left，那么价值呢？本题是求装满背包的组合数，因此，可以使用dp[i][j]表示用下标[0,i]的数字去装满容量为j的背包，满足条件的组合数;
递推公式：dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]] ;当前的组合数=使用下标[0,i-1]装满背包j的组合数+使用下标[0,i-1]装满背包j-nums[i]的组合数 ;
当使用滚动数组的时候：dp[j]=dp[j]+dp[j-nums[i]]
代码：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//如何转换为动态规划：数组可以分成两部分left和right ；left+right=sum，left-right=target
//left=(sum+target)/2
//相当于要在数组中找出和为left的组合数
//递推公式：dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
int sum=0;
for(auto i:nums) sum+=i;
//target>sum 返回0
if(target>sum) return 0;
//sum+target为奇数，返回0
if((sum+target)&0x01) return 0;
int bagSize=(sum+target)/2;
vector<int> dp(bagSize+1,0);
dp[0]=1;
for(int i=0;i<nums.size();++i)
{
for(int j=bagSize;j>=nums[i];--j)
{
dp[j]+=dp[j-nums[i]];
}
}
return dp[bagSize];
}
};
总结：动规五部曲
-
确定
dp数组以及下标含义；dp[j]表示装满容量为j的背包的组合数 -
确定递推公式；
dp[j]+=dp[j-nums[i]] -
dp初始化；dp[0]=1是其他dp推导的基础例如： nums = [1,1,1,1,1], target = 3
dp数组打印出来是：1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
1 5 10 10 5dp[4]=dp[4]+dp[3] =0
dp[3]=dp[3]+dp[2] =0
dp[2]=dp[2]+dp[1] =0
dp[1]=dp[1]+dp[0] =1
-
确定遍历的顺序；先遍历物品，再遍历背包
-
举例推导
dp数组；
474 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
似懂非懂的只好记下来了
01背包和完全背包的区别是：物品的数量有几个,只能选一次是01背包，可以选多次是完全背包
本题，物品是字符串，只能选一次，所以是01背包 ，不同的是背包有两个维度，相当于有两个空间，一个空间装0一个空间装1
-
确定dp
dp[i][j]：最多有i个0和j个1的strs的⼦集的最大大小 -
递推公式
dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)其中，
zeroNum和oneNum分别表示当前字符串中的0和1的个数如何不使用滚动数组的话，
dp可以定义成三维的dp[k][i][j]dp[k][i][j]=max(dp[k-1][i][j],dp[k-1][i-zeroNum][j-oneNum]+1) -
初始化
当背包容量小于
oneNum和zeroNum的时候，初始化为0； -
遍历顺序
01背包遍历是先遍历物品，再遍历背包，这里也是一样for(int k=0;k<strs.size();++k)//遍历物品 { int zeroNum=0,oneNum=0; for(auto ch:strs[k]) { if(ch=='0') zeroNum++; else oneNum++; } for(int i=m;i>=zeroNum;--i)//遍历背包0 { for(int j=n;j>=oneNum;--j)//遍历背包1 { dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1); } } }代码
class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m+1,vector<int>(n+1,0)); for(int k=0;k<strs.size();++k)//遍历物品 { int zeroNum=0,oneNum=0; for(auto ch:strs[k]) { if(ch=='0') zeroNum++; else oneNum++; } for(int i=m;i>=zeroNum;--i)//遍历背包0 { for(int j=n;j>=oneNum;--j)//遍历背包1 { dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1); } } } return dp[m][n]; } };
京公网安备 11010502036488号