动态规划—背包问题
前言：1.背包问题就是一种组合优化的NP完全问题
2.01背包问题是其他背包问题的理解基础
一.01背包
1.模板题【模板】01背包_牛客题霸_牛客网
<1>状态表式：
(1)不要求装满背包：dp[i][j]表示：在前i个物品中挑选，总体积不超过j，所有选法中，所能挑选的最大价值
(2)要求装满背包：dp[i][j]表示：在前i个物品中挑选，总体积等于j，所有选法中，所能挑选的最大价值
<2>状态转移方程：
(1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
(2)当要求装满背包时，用-1代表这种选法不成立，此时若是挑选i号物品，不仅要求j>=v[i]，还要要求dp[i-1][j-v[i]]!=-1
<3>初始化：多开一行和一列
(1)当有0个物品时，想要总体积不超过j，只要不选物品即可，此时最大价值为0，故初始值均设为0
(2)当有0个物品时，想要总体积等于0，只要不选物品即可，此时dp[0][0]=0;但当有0个物品时，想要总体积等于j，不存在这种可能，故dp[0][j]=-1(j>=1)
<4>填表顺序:从上往下，从左往右填
<5>返回值：dp[n][V]
<6>代码实现
#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
int v[1001],w[1001];
int n,V;
int main() {
//读入数据
cin>>n>>V;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
vector<vector<int>> dp(n+1,vector<int>(V+1));
//不要求装满背包
for(int i=1;i<=n;i++)
{
for(int j=0;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=0;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])<<endl;
return 0;
}<7>空间优化:利用滚动数组
填第i行时只需用到第i-1行的第j列和第j-v[i]列数据，如此便可利用一维数组完成统计，此时状态转移方程为dp[j]=max(dp[j],dp[j-v[i]]+w[i])(j>=v[i])
注：为了保证第i-1行的第j-v[i]列数据不被覆盖，填表时需要从右往左填
<8>优化后的代码
#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
int v[1001],w[1001];
int n,V;
int main() {
//读入数据
cin>>n>>V;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
vector<int> dp(V+1);
//不要求装满背包
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];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--)
{
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.01背包的特点：对于一个只有选与不选两种情况，且一个物品至多选一次
二.完全背包
1.模板题【模板】完全背包_牛客题霸_牛客网
<1>状态表式：
(1)不要求装满背包：dp[i][j]表示：在前i个物品中挑选，总体积不超过j，所有选法中，所能挑选的最大价值
(2)要求装满背包：dp[i][j]表示：在前i个物品中挑选，总体积等于j，所有选法中，所能挑选的最大价值
<2>状态转移方程：
(1) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
(2)当要求装满背包时，用-1代表这种选法不成立，此时若是挑选i号物品，不仅要求j>=v[i]，还要要求dp[i-1][j-v[i]]!=-1
<3>初始化：多开一行和一列
(1)当有0个物品时，想要总体积不超过j，只要不选物品即可，此时最大价值为0，故初始值均设为0
(2)当有0个物品时，想要总体积等于0，只要不选物品即可，此时dp[0][0]=0;但当有0个物品时，想要总体积等于j，不存在这种可能，故dp[0][j]=-1(j>=1)
<4>填表顺序：从上往下，从左往右填
<5>返回值：dp[n][V];
<6>代码实现:
#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=1001;
int n,V;
int v[N],w[N];
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
vector<vector<int>> dp(n+1,vector<int>(V+1);
//第一问
//dp[i][j]:从前i个物品里面选，总体积不超过j，所有选法中能挑选出来的最大价值
for(int i=1;i<=n;i++)//物品个数
{
for(int j=0;j<=V;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i]) dp[i][j]=max(dp[i][j],w[i]+dp[i][j-v[i]]);
}
}
cout<<dp[n][V]<<endl;
//第二问
//dp[i][j]:从前i个物品里面选，总体积正好为j，所有选法中能挑选出来的最大价值
memset(dp,0,sizeof(dp));
//dp[i][j]==-1：不存在该种情况
for(int i=1;i<=V;i++) dp[0][i]=-1;//初始化
for(int i=1;i<=n;i++)//物品个数
{
for(int j=0;j<=V;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i] && dp[j-v[i]]!=-1)
dp[i][j]=max(dp[i][j],w[i]+dp[i][j-v[i]]);
}
}
cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;
return 0;
}<7>空间优化:
填第i行时只需用到第i-1行的第j列和第i行的第j-v[i]列数据，如此便可利用一维数组完成统计，此时状态转移方程为dp[j]=max(dp[j],dp[j-v[i]]+w[i])(j>=v[i])
注：填表时需要从左往右填即可，不会出现覆盖
<8>优化后的代码
#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=1001;
int n,V;
int v[N],w[N];
int dp[N];
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
//第一问
//dp[i][j]:从前i个物品里面选，总体积不超过j，所有选法中能挑选出来的最大价值
for(int i=1;i<=n;i++)//物品个数
{
for(int j=v[i];j<=V;j++)
{
dp[j]=max(dp[j],w[i]+dp[j-v[i]]);
}
}
cout<<dp[V]<<endl;
//第二问
//dp[i][j]:从前i个物品里面选，总体积正好为j，所有选法中能挑选出来的最大价值
memset(dp,0,sizeof(dp));
//dp[i][j]==-1：不存在该种情况
for(int i=1;i<=V;i++) dp[i]=-1;//初始化
for(int i=1;i<=n;i++)//物品个数
{
for(int j=v[i];j<=V;j++)
{
if(dp[j-v[i]]!=-1)
dp[j]=max(dp[j],w[i]+dp[j-v[i]]);
}
}
cout<<(dp[V]==-1?0:dp[V])<<endl;
return 0;
}
2.完全背包的特点：对于某个物品可以选多个
三.二维费用的背包问题
本质：就是有两个限制条件的背包问题
例题：一和零474. 一和零 - 力扣（LeetCode）
本质：有两个限制条件的01背包问题
1.状态表示:dp[i][j][k]表示：从前i个字符串中挑选字符，字符0的个数不超过j，字符1的个数不超过k，所有选法中的最大长度
2.状态转移方程:具体分析过程见01背包问题
3.初始化:初始值设为0
5.返回值：dp[len][m][n]
6.代码实现：
int findMaxForm(vector<string>& strs, int m, int n) {
int len=strs.size();
//动态规划解决问题
vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1));
for(int i=1;i<=len;i++)
{
//统计每个字符串中0和1的个数
int a=0,b=0;
for(char ch:strs[i-1])
{
if(ch=='0') a++;
else b++;
}
for(int j=0;j<=m;j++)
{
for(int k=0;k<=n;k++)
{
dp[i][j][k]=dp[i-1][j][k];
if(j>=a && k>=b) dp[i][j][k]=max(dp[i][j][k],dp[i][j-a][k-b]+1);
}
}
}
return dp[len][m][n];
}7.空间优化：具体分析参考01背包问题
8.优化后的代码：
int findMaxForm(vector<string>& strs, int m, int n) {
int len=strs.size();
//动态规划解决问题
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=1;i<=len;i++)
{
//统计每个字符串中0和1的个数
int a=0,b=0;
for(char ch:strs[i-1])
{
if(ch=='0') a++;
else b++;
}
for(int j=m;j>=a;j--)
{
for(int k=n;k>=b;k--)
{
dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);
}
}
}
return dp[m][n];
}更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)