DP：01背包问题
一、背包问题的概述
背包问题是⼀种组合优化的NP完全问题。 本质上是为了找出“带有限制条件的组合最优解”
1、根据物品的个数，分为如下几类：
• 01背包问题：每个物品只有⼀个（重点掌握） • 完全背包问题：每个物品有无限多个（重点掌握） • 多重背包问题：每件物品最多有n个 • 混合背包问题：每个物品会有上⾯三种情况 • 分组背包问题：物品有n组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品
2、根据背包是否装满，⼜分为两类
• 不⼀定装满背包（重点） • 背包⼀定装满（重点）
3、优化方案
• 空间优化：滚动数组（重点掌握） • 单调队列优化 • 贪心优化
4、根据限定条件的个数，⼜分为两类
• 限定条件只有⼀个：比如体积->普通的背包问题（重点） • 限定条件有两个：比如体积+重量->⼆维费用背包问题（重点）
5、根据不同的问法，⼜分为很多类：
• 输出方案 • 求方案总数 • 最优方案 • 方案可行性
背包问题的题型非常多样，其中最重要以及基础的就是01背包和完全背包以及背包是否装满的讨论（会通过牛客的两道模版题探究），还有滚动数组的优化策略（ 在以往的动态规划中，我们几乎很少去谈论空间优化，因为对于一道dp题来说，能解决出来就已经很不容易了，我们不太会关注其空间复杂度。但是在背包问题中，滚动数组的优化是有一定套路可言的，并且在某些情况下对时间也是有一定优化的！！）
二、01背包[模版]
#include<iostream>
#include<string.h>
using namespace std;
//定义成全局，就不用在栈里面进行初始化，并且我们可以在栈上开辟的空间更大
const int N=1001;
int n,V,v[N],w[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];//不选第i个物品的情况
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);//修改成0
//先进行初始化
for(int j=1;j<=V;++j) dp[0][j]=-1;//跟0区分开
for(int i=1;i<=n;++i)
for(int j=1;j<=V;++j)
{
dp[i][j]=dp[i-1][j];//不选第i个物品的情况
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;
}滚动数组优化（空间复杂度N^2——>N 时间复杂度常数提升）
#include<iostream>
#include<string.h>
using namespace std;
//定义成全局，就不用在栈里面进行初始化，并且我们可以在栈上开辟的空间更大
const int N=1001;
int n,V,v[N],w[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=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);//修改成0
//先进行初始化
for(int j=1;j<=V;++j) dp[j]=-0x3f3f3f3f;//跟0区分开
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]<0?0:dp[V])<<endl;
}对于不存在的状态，因为我们该题中要求的是max，所以我们设成-0x3f3f3f3f保证该状态不被选到，设置成这个的原因是避免了越界的风险同时又保证了不存在的状态是小于0的，且不会影响填报！！
三、和为目标和的最长子序列长度
这题就是非常明显的01背包问题，其中每个数只有选或者不选，目标值相当于是容量，且要刚刚好。 dp[i][j]表示从前i个数选，和恰好为j的最长子序列。
class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
int n=nums.size();
//01背包问题 dp[i][j]表示从前i个数选择 正好凑成j的的子序列的最长长度
vector<vector<int>> dp(n+1,vector<int>(target+1));
//分析状态转移方程 dp[i][j]
//如果我不选i dp[i-1][j]
//如果我选i dp[i-1][j-nums[i-1]]+1
//初始化 如果i为0无数可选 没有这个状态
for(int j=1;j<=target;++j) dp[0][j]=-0x3f3f3f3f;//给一个小的值 保证选最大值的时不会被选上
for(int i=1;i<=n;++i)
for(int j=0;j<=target;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=nums[i-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1]]+1);
}
return dp[n][target]<0?-1:dp[n][target];
}
};滚动数组优化：
class Solution {
public:
int lengthOfLongestSubsequence(vector<int>& nums, int target) {
int n=nums.size();
//01背包问题 dp[i][j]表示从前i个数选择 正好凑成j的的子序列的最长长度
vector<int> dp(target+1,-0x3f3f3f3f);
//分析状态转移方程 dp[i][j]
//如果我不选i dp[i-1][j]
//如果我选i dp[i-1][j-nums[i-1]]+1
//初始化 如果i为0无数可选 没有这个状态
dp[0]=0;
for(int i=1;i<=n;++i)
for(int j=target;j>=nums[i-1];--j)
dp[j]=max(dp[j],dp[j-nums[i-1]]+1);
return dp[target]<0?-1:dp[target];
}
};四、分割等和子集（需转化）
该题并不能直接用01背包问题，首先需要先将问题进行转化——在数组中选一些数，让这些数的和为sum/2。
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int sum=accumulate(nums.begin(),nums.end(),0);
if(sum%2) return false;//是奇数，直接返回
//是偶数的时候 dp[i][j]表示从前i个数中选，所有选法中能否凑成j这个数
int aim=sum/2;
int n=nums.size();
vector<vector<bool>> dp(n+1,vector<bool>(aim+1));
//初始化，当j=0时，显然都是true 当i=0时，必然为false
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)
//不选i的话 dp[i][j]=dp[i-1][j]
//选i的话 dp[i][j]=dp[i-1][j-nums[i-1]] 前提j>=nums[i-1]
{
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];
}
};滚动数组优化：
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int sum=accumulate(nums.begin(),nums.end(),0);
if(sum%2) return false;//是奇数，直接返回
//是偶数的时候 dp[i][j]表示从前i个数中选，所有选法中能否凑成j这个数
int aim=sum/2;
int n=nums.size();
vector<bool> dp(aim+1);
//初始化，当j=0时，显然都是true 当i=0时，必然为false
dp[0]=true;
//开始填表
for(int i=1;i<=n;++i)
for(int j=aim;j>=nums[i-1];--j)
//不选i的话 dp[i][j]=dp[i-1][j]
//选i的话 dp[i][j]=dp[i-1][j-nums[i-1]] 前提j>=nums[i-1]
dp[j]=dp[j]||dp[j-nums[i-1]];
return dp[aim];
}
};五、目标和（需转化）
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 从nums中选择一些数能够凑成sum+target/2 转化成01背包问题
int sum=accumulate(nums.begin(),nums.end(),0);
int aim=(sum+target)>>1;
if(aim<0||(sum+target)%2) return 0;
int n=nums.size();
//dp[i][j] 从前i个数选 变成j有多少种选法
//如果不选i dp[i-1][j]
//如果选i +=dp[i-1][j-nums[i-1]]
//分析初始化 i=0的时候 必为0 j=0的时候 不好判断，因为nums[i]可能是0
//但是不需要初始化，因为要满足j>=nums[i] 那么nums[i]必然要为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];
}
};滚动数组优化：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 从nums中选择一些数能够凑成sum+target/2 转化成01背包问题
int sum=accumulate(nums.begin(),nums.end(),0);
int aim=(sum+target)>>1;
if(aim<0||(sum+target)%2) return 0;
int n=nums.size();
//dp[i][j] 从前i个数选 变成j有多少种选法
//如果不选i dp[i-1][j]
//如果选i +=dp[i-1][j-nums[i-1]]
//分析初始化 i=0的时候 必为0 j=0的时候 不好判断，因为nums[i]可能是0
//但是不需要初始化，因为要满足j>=nums[i] 那么nums[i]必然要为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];
}
};六、最后一块石头的重量||(需转化)
class Solution {
public:
int lastStoneWeightII(vector<int>& nums) {
//让一堆里面的数尽可能接近sum/2
int sum=accumulate(nums.begin(),nums.end(),0);
int aim=sum/2,n=nums.size();
//dp[i][j]表示从前i个数选择，总和不超过j，此时所有元素的最大和
vector<vector<int>> dp(n+1,vector<int>(aim+1));
//分析初始化 如果都为0 就返回0 如果i为0 也是0 如果j为0 不用初始化
for(int i=1;i<=n;++i)
for(int j=1;j<=aim;++j)
{
//如果不选i dp[i-1][j]
//如果选i dp[i-1][j-nums[i-1]] 找最大和
dp[i][j]=dp[i-1][j];
if(j>=nums[i-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
}
return sum-2*dp[n][aim];
}
};滚动数组优化：
class Solution {
public:
int lastStoneWeightII(vector<int>& nums) {
//让一堆里面的数尽可能接近sum/2
int sum=accumulate(nums.begin(),nums.end(),0);
int aim=sum/2,n=nums.size();
//dp[i][j]表示从前i个数选择，总和不超过j，此时所有元素的最大和
vector<int> dp(aim+1);
//分析初始化 如果都为0 就返回0 如果i为0 也是0 如果j为0 不用初始化
//如果不选i dp[i-1][j]
//如果选i dp[i-1][j-nums[i-1]] 找最大和
for(int i=1;i<=n;++i)
for(int j=aim;j>=nums[i-1];--j)
dp[j]=max(dp[j],dp[j-nums[i-1]]+nums[i-1]);
return sum-2*dp[aim];
}
};七、将一个数字表示成幂的和的方案数
知识点1：double不支持取模，需要取模又担心溢出只能使用long long
知识点2：pow函数是求数的任意次幂
知识点3:10^9+7相当于1e9+7
class Solution {
public:
int numberOfWays(int n, int x) {
//统计方案数
//dp[i][j]表示从前i个数的x次幂之和 恰好等于j 的方案数
//i=0时 无数可选 方案肯定是
const int N=1e9+7;
vector<vector<long long>> dp(n+1,vector<long long>(n+1)); //double不支持取模
dp[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
{
//不选i dp[i][j]=dp[i-1][j]
//选i dp[i][j]+=dp[i-1][j-pow(i,x)]
dp[i][j]=dp[i-1][j];
long long p=pow(i,x);
if(j>=p) dp[i][j]+=dp[i-1][j-p];
dp[i][j]%=N;
}
return dp[n][n];
}
};滚动数组优化：
class Solution {
public:
int numberOfWays(int n, int x) {
//统计方案数
//dp[i][j]表示从前i个数的x次幂之和 恰好等于j 的方案数
//i=0时 无数可选 方案肯定是
const int N=1e9+7;
vector<long long> dp(n+1); //double不支持取模
dp[0]=1;
for(int i=1;i<=n;++i)
{
long long p=pow(i,x);
for(int j=n;j>=p;--j)
//不选i dp[i][j]=dp[i-1][j]
//选i dp[i][j]+=dp[i-1][j-pow(i,x)]
dp[j]=(dp[j]+dp[j-p])%N;
}
return dp[n];
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-06-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录