25年开篇之作---动态规划系列＜七＞ 01背包问题
目录
一：背包问题的简介
二:01背包问题
1.模板题
2.LeetCode经典例题
一：背包问题的简介
背包问题 (Knapsack problem) 是⼀种组合优化的
NP完全问题
。
问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。
1.根据物品的个数，分为如下⼏类：01 背包问题：每个物品只有⼀个完全背包问题：每个物品有⽆限多个多重背包问题：每件物品最多有 si 个混合背包问题：每个物品会有上⾯三种情况......分组背包问题：物品有 n 组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品
2.其中上述分类⾥⾯，根据背包是否装满，⼜分为两类：不⼀定装满背包背包⼀定装满
3.优化⽅案：空间优化 - 滚动数组单调队列优化贪⼼优化
4.根据限定条件的个数，⼜分为两类：限定条件只有⼀个：⽐如体积 -> 普通的背包问题限定条件有两个：⽐如体积 + 重量 -> ⼆维费⽤背包问题
5.根据不同的问法，⼜分为很多类：输出⽅案求⽅案总数最优⽅案⽅案可⾏性
其实还有很多分类，但是我们仅需了解即可。
二:01背包问题
1.模板题
OJ传送门 牛客网 DP41 【模板】01背包
画图分析:
使用动态规划解决(第一问与第二问雷同，绿色标记的为第二问的不同之处)
对于01背包问题每个位置都是选与不选，因此是一个线性的dp问题
1.状态表示
dp[i]表示从前i个物品中挑选，所有选法中，能挑选出来的最大价值
但用此状态填写dp表时，对于最近的一步，即i号物品是否挑选，若挑选的话，就得使用前面的状态来更新dp[i]，但前面的状态只知道最大价值，并不知背包的体积，可能背包的体积已经放不下i号物品了，因此可以考虑将体积加上，增加一维
dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有的选法中，能挑选出来的最大价值
dp[i][j]表示从前i个物品中挑选，总体积正好等于j，所有的选法中，能挑选出来的最大价值
2.状态转移方程
3.初始化
4.填表顺序 从上往下
5.返回值 dp[n][V]
具体代码:
#include <iostream>
#include <string.h>
using namespace std;
//使用全局变量
const int N=1010;
int n,V,w[N],v[N];
int dp[N][N];
int main()
{
//输入变量
cin>>n>>V;
for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
//解决第一问
for(int i=1;i<=n;++i)
{
for(int j=1;j<=V;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
cout<<dp[n][V]<<endl;
//解决第二问
memset(dp,0,sizeof(dp));
for(int j=1;j<=V;++j) dp[0][j]=-1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=V;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i] && dp[i-1][j-v[i]]!=-1)
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
cout<<(dp[n][V]==-1? 0:dp[n][V]);
return 0;
}6.做优化
利用滚动数组做空间上的优化，直接在原始代码上稍加修改即可(删除所有的横坐标，修改一下j的遍历顺序)
优化后的代码:
#include <iostream>
#include <string.h>
using namespace std;
//使用全局变量
const int N=1010;
int n,V,w[N],v[N];
int dp[N];
int main()
{
//输入变量
cin>>n>>V;
for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
//解决第一问
for(int i=1;i<=n;++i)
{
for(int j=V;j>=v[i];--j)//修改遍历顺序
{
//dp[j]=dp[j];
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[V]<<endl;
//解决第二问
memset(dp,0,sizeof(dp));
for(int j=1;j<=V;++j) dp[j]=-1;
for(int i=1;i<=n;++i)
{
for(int j=V;j>=v[i];--j)
{
//dp[j]=dp[j];
if(dp[j-v[i]]!=-1)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<(dp[V]==-1? 0:dp[V])<<endl;
return 0;
}2.LeetCode经典例题
OJ传送门 LeetCode<416>分割等和子集
画图分析:
如果直接做的话，会有点不好做，可以将问题转化下，最终整个数组要划分为相等的两部分，即sum/2（sum为整个数组的和），此时就转化为在数组中选一些数出来，让这些数的和为sum/2.
这就类似于01背包问题，背包的体积为sum/2,然后遍历整个数组，确定每个位置选还是不选
使用动态规划解决
1.状态表示
dp[i][j]表示从前i个数中选，所有的选法中，是否能凑成j这个数
2.状态转移方程
3.初始化
4.填表顺序 从上往下
5.返回值 dp[n][sum/2]
优化前及优化后的代码
bool canPartition(vector<int>& nums)
{
int n=nums.size(),sum=0;
for(auto x:nums) sum+=x;
if(sum%2) return false;
int aim=sum/2;
vector<vector<bool>> dp(n+1,vector<bool>(aim+1));
for(int i=0;i<=n;++i) dp[i][0]=true;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=aim;++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[n][aim];
}
//优化后
bool canPartition(vector<int>& nums)
{
int n=nums.size(),sum=0;
for(auto x:nums) sum+=x;
if(sum%2) return false;
int aim=sum/2;
vector<bool>dp(aim+1);
dp[0]=true;
for(int i=1;i<=n;++i)
{
for(int j=aim;j>=nums[i-1];--j)
{
dp[j]=dp[j] || dp[j-nums[i-1]];
}
}
return dp[aim];
}OJ传送门 LeetCode<494>目标和
画图分析:
先进行预处理转化一下，再用动态规划解决
使用动态规划解决
1.状态表示
dp[i][j]表示从前i个数中挑选，总和刚好为a的选法有多少种
2.状态转移方程
3.初始化
4.填表顺序 从上往下
5.返回值 dp[n][a]
优化前的代码和优化后的
int findTargetSumWays(vector<int>& nums, int target)
{
int sum=0,n=nums.size();
for(auto x:nums) sum+=x;
int aim=(sum+target)/2;
//处理一下边界条件
if(aim<0 || (sum+target)%2) return 0;
vector<vector<int>> dp(n+1,vector<int>(aim+1));
dp[0][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=aim;++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[n][aim];
}
//优化后
int findTargetSumWays(vector<int>& nums, int target)
{
int sum=0,n=nums.size();
for(auto x:nums) sum+=x;
int aim=(sum+target)/2;
//处理一下边界条件
if(aim<0 || (sum+target)%2) return 0;
vector<int>dp(aim+1);
dp[0]=1;
for(int i=1;i<=n;++i)
{
for(int j=aim;j>=nums[i-1];--j)
dp[j]+=dp[j-nums[i-1]];
}
return dp[aim];
}OJ传送门 LeetCode<1049>最后一块石头的重量 II
画图分析:
在使用动态规划之前将问题预处理转化一下
使用动态规划解决
1.状态表示
dp[i][j]表示从前i个数中挑选，总和不超过j，此时的最大和
2.状态转移方程
3.初始化 只需要根据状态表示初始化第一行即可
4.填表顺序 从上往下
5.返回值 sum-2*dp[n][sum/2]
具体代码
int lastStoneWeightII(vector<int>& stones)
{
int n=stones.size(),sum=0;
for(auto x:stones) sum+=x;
int m=sum/2;
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;++i)
{
for(int j=0;j<=m;++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[n][m];
}
//优化后
int lastStoneWeightII(vector<int>& stones)
{
int n=stones.size(),sum=0;
for(auto x:stones) sum+=x;
int m=sum/2;
vector<int>dp(m+1);
for(int i=1;i<=n;++i)
{
for(int j=m;j>=stones[i-1];--j)
{
dp[j]=max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
}
}
return sum-2*dp[m];
}