DP：01背包问题

2024-06-17 07:20
文章标签 dp 01 背包 问题

本文主要是介绍DP：01背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、背包问题的概述

背包问题是⼀种组合优化的NP完全问题。
本质上是为了找出“带有限制条件的组合最优解”

1、根据物品的个数，分为如下几类：

• 01背包问题：每个物品只有⼀个（重点掌握）
• 完全背包问题：每个物品有无限多个（重点掌握）
• 多重背包问题：每件物品最多有n个
• 混合背包问题：每个物品会有上⾯三种情况
• 分组背包问题：物品有n组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品

2、根据背包是否装满，⼜分为两类

• 不⼀定装满背包（重点）
• 背包⼀定装满（重点）

3、优化方案

• 空间优化：滚动数组（重点掌握）
• 单调队列优化
• 贪心优化

4、根据限定条件的个数，⼜分为两类

• 限定条件只有⼀个：比如体积->普通的背包问题（重点）
• 限定条件有两个：比如体积+重量->⼆维费用背包问题（重点）

5、根据不同的问法，⼜分为很多类：

• 输出方案
• 求方案总数
• 最优方案
• 方案可行性

        背包问题的题型非常多样，其中最重要以及基础的就是01背包和完全背包以及背包是否装满的讨论（会通过牛客的两道模版题探究），还有滚动数组的优化策略（ 在以往的动态规划中，我们几乎很少去谈论空间优化，因为对于一道dp题来说，能解决出来就已经很不容易了，我们不太会关注其空间复杂度。但是在背包问题中，滚动数组的优化是有一定套路可言的，并且在某些情况下对时间也是有一定优化的！！）

二、01背包[模版]

【模板】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的，且不会影响填报！！

三、和为目标和的最长子序列长度

. - 力扣（LeetCode）

       这题就是非常明显的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];}
};

四、分割等和子集（需转化）

. - 力扣（LeetCode）

该题并不能直接用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时，必然为falsefor(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时，必然为falsedp[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];}
};

 五、目标和（需转化）

. - 力扣（LeetCode）

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];}
};

六、最后一块石头的重量||(需转化)

. - 力扣（LeetCode）

class Solution {
public:int lastStoneWeightII(vector<int>& nums) {//让一堆里面的数尽可能接近sum/2int 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/2int 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];}
};

七、将一个数字表示成幂的和的方案数

. - 力扣（LeetCode）

知识点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];}
};

 

这篇关于DP：01背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1068800。

相关文章

linux生产者，消费者问题

linux生产者，消费者问题

pthread_cond_wait() ：用于阻塞当前线程，等待别的线程使用pthread_cond_signal()或pthread_cond_broadcast来唤醒它。 pthread_cond_wait() 必须与pthread_mutex 配套使用。pthread_cond_wait()函数一进入wait状态就会自动release mutex。当其他线程通过pthread
阅读更多...
问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 #其他#学习方法#微信

问题：第一次世界大战的起止时间是 A.1913 ~1918 年 B.1913 ~1918 年 C.1914 ~1918 年 D.1914 ~1919 年 参考答案如图所示
阅读更多...
2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

2024.6.24 IDEA中文乱码问题（服务器 控制台 TOMcat）实测已解决

1.问题产生原因： 1.文件编码不一致：如果文件的编码方式与IDEA设置的编码方式不一致，就会产生乱码。确保文件和IDEA使用相同的编码，通常是UTF-8。2.IDEA设置问题：检查IDEA的全局编码设置和项目编码设置是否正确。3.终端或控制台编码问题：如果你在终端或控制台看到乱码，可能是终端的编码设置问题。确保终端使用的是支持你的文件的编码方式。 2.解决方案： 1.File -> S
阅读更多...
vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

vcpkg安装opencv中的特殊问题记录（无法找到opencv_corexd.dll）

我是按照网上的vcpkg安装opencv方法进行的（比如这篇：从0开始在visual studio上安装opencv（超详细，针对小白）），但是中间出现了一些别人没有遇到的问题，虽然原因没有找到，但是本人给出一些暂时的解决办法： 问题1： 我在安装库命令行使用的是 .\vcpkg.exe install opencv 我的电脑是x64，vcpkg在这条命令后默认下载的也是opencv2:x6
阅读更多...
问题-windows-VPN不正确关闭导致网页打不开

问题-windows-VPN不正确关闭导致网页打不开

为什么会发生这类事情呢？ 主要原因是关机之前vpn没有关掉导致的。 至于为什么没关掉vpn会导致网页打不开，我猜测是因为vpn建立的链接没被更改。 正确关掉vpn的时候，会把ip链接断掉，如果你不正确关掉，ip链接没有断掉，此时你vpn又是没启动的，没有域名解析，所以就打不开网站。 你可以在打不开网页的时候，把vpn打开，你会发现网络又可以登录了。 方法一 注意：方法一虽然方便，但是可能会有
阅读更多...
C++入门01

C++入门01

1、.h和.cpp 源文件 (.cpp)源文件是C++程序的实际实现代码文件，其中包含了具体的函数和类的定义、实现以及其他相关的代码。主要特点如下：实现代码: 源文件中包含了函数、类的具体实现代码，用于实现程序的功能。编译单元: 源文件通常是一个编译单元，即单独编译的基本单位。每个源文件都会经过编译器的处理，生成对应的目标文件。包含头文件: 源文件可以通过#include指令引入头文件，以使
阅读更多...
vue同页面多路由懒加载-及可能存在问题的解决方式

vue同页面多路由懒加载-及可能存在问题的解决方式

先上图，再解释 图一是多路由页面，图二是路由文件。从图一可以看出每个router-view对应的name都不一样。从图二可以看出层路由对应的组件加载方式要跟图一中的name相对应，并且图二的路由层在跟图一对应的页面中要加上components层，多一个s结尾，里面的的方法名就是图一路由的name值，里面还可以照样用懒加载的方式。 页面上其他的路由在路由文件中也跟图二是一样的写法。 附送可能存在
阅读更多...
vue+elementui--$message提示框被dialog遮罩层挡住问题解决

vue+elementui--$message提示框被dialog遮罩层挡住问题解决

最近碰到一个先执行this.$message提示内容，然后接着弹出dialog带遮罩层弹框。那么问题来了，message提示框会默认被dialog遮罩层挡住，现在就是要解决这个问题。 由于都是弹框，问题肯定是出在z-index比重问题。由于用$message方式是写在js中而不是写在html中所以不是很好直接去改样式。 不过好在message组件中提供了customClass 属性，我们可以利用
阅读更多...
Visual Studio中，MSBUild版本问题

Visual Studio中，MSBUild版本问题

假如项目规定了MSBUild版本，那么在安装完Visual Studio后，假如带的MSBUild版本与项目要求的版本不符合要求，那么可以把需要的MSBUild添加到系统中，然后即可使用。步骤如下：            假如项目需要使用V12的MSBUild，而安装的Visual Studio带的MSBUild版本为V14。 ①到MSDN下载V12 MSBUild包，把V12包解压到目录（
阅读更多...
YOLO v3 训练速度慢的问题

YOLO v3 训练速度慢的问题

一天一夜出了两个模型，仅仅迭代了200次   原因：编译之前没有将Makefile 文件里的GPU设置为1，编译的是CPU版本，必须训练慢   解决方案： make clean  vim Makefile make   再次训练 速度快了，5分钟迭代了500次
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2