卡玛网● 46. 携带研究材料 ● 01背包问题,你该了解这些! 滚动数组 力扣● 416. 分割等和子集

开始背包问题,掌握0-1背包和完全背包即可,注:0-1背包是完全背包的基础。

0-1背包问题:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。下面是n=4的例子:

如果用穷举方法,应该使用回溯法,那么每个物件都有放一个和不放两种选择,所以回溯的时间复杂度是O(2^n),达到指数级。所以要使用动态规划。

以这个例题来进行二维dp数组和一维dp数组的动规五部曲:背包最大重量为4。物品为:

重量价值
物品0115
物品1320
物品2430

问背包能背的物品最大价值是多少?
 

● 二维dp数组

1. 确定动规数组元素的含义。使用的是二维数组 dp[i][j]:从物品[0,i]范围内随便选择,放进容量为j的背包里,dp[i][j]是背包的最大价值。如下图所示:

2. 确定递推公式。我们可以根据两种方式得到dp[i][j],两种方式对应两种情况,其实dp[i][j]就是取这两种情况的最大值。

①不放物品 i。如果物品i放进重量为j的背包会超重,那么不能把i放进去,所以重量设定为j的话,从[0,i-1]选择和从[0,i]选择的最大价值是一样,所以 dp[i][j] = dp[i-1][j] 。

②放物品 i。如果不会超重,可以放进去。物品 i 放进去,背包最大重量为 j ,还没有放进去物品 i 的时候,背包的最大重量为 j - weight[i] ,数量为i-1,所以这时背包的最大价值为 dp[ i-1 ][ j - weight[i] ]。加入物品 i ,背包价值 dp[i][j] 就为 dp[ i-1 ][ j - weight[i] ] + value[i] 。

所以dp[i][j]= max ( dp[i-1][j] , dp[ i-1 ][ j - weight[i] ] + value[i] )。

必须牢记dp[i][j]的含义。

3. 如何初始化。

在上图里面,背包重量j为0的时候,什么也不能放进去,所以这一列肯定都是0。

物品 0 那一行,只能选择物品 0 自己,所以背包重量 j >=物品 0 的重量对应的表格都应该填上物品 0 的价值15.所以初始化后:

4. 遍历顺序。 根据上表,第一行第一列已经初始化,所以 i 应该从12,j 从 0 到背包容量4。是先行还是先列呢,其实都一样。先每个物品那一行统计完更好理解一些,但是先列也是从上往下走的,到一个元素的时候,左上角(包括正上方)的dp[i][j]都已经统计完成,所以都可以。背包问题里,两个for循环的先后循序是非常有讲究的。

5. 打印dp数组。

最后的结果就是返回dp[2][4]。

做题巩固一下:

题目链接46. 携带研究材料:题目链接

和上面例题的分析过程一样,使用二维dp数组,代码如下:

void maxValue(){
    int m,begweight;//M 代表物品的种类数,begweight是背包容量
    cin>>m>>begweight;
    vector<int> weight(m);
    vector<int> value(m);
    //读取重量和价值
    for(int i=0;i<m;++i){
        cin>>weight[i];
    }
    for(int i=0;i<m;++i){
        cin>>value[i];
    }
    //注意行列数
    vector<vector<int>> dp(m,vector<int>(begweight+1,0));
    //初始化
    for(int j=0;j<m;++j){
        dp[j][0]=0;
    }
    for(int j=weight[0];j<=begweight;++j){
        dp[0][j]=value[0];
    }
    //递推
    for(int i=1;i<m;++i){
        for(int j=1;j<=begweight;++j){
            //物品i重量超过背包容量,肯定不放进去
            if(j<weight[i]) dp[i][j]=dp[i-1][j];       
            //物品i重量小于背包容量,也不一定能放进去,取max
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    cout<< dp[m-1][begweight] << endl;
}

● 一维滚动数组 

在上面使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);所以dp[i-1]这一层的得到之后,就拷贝到对应的dp[i]这一层来(dp[i]左上方的dp[i-1]肯定都已经得到),这个递推公式可以把 dp[ i-1] 的都改为dp[ i ]:

dp[ i ][ j ] = max(dp[ i ][ j ], dp[ i ][ j - weight[ i ] ] + value[ i ]);

与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组,只留下了上面二维数组的列)。

动规五部曲分析如下:

1. dp[j]含义。含量是j的背包能装下的最大价值。可以从所有的物品中选择。

2. 递推公式。其实和二维数组是差不多的意思,两种情况:放 i 和不放 i 。dp数组省略了i所以这个递推公式也去掉i:dp[ j ] = max(dp[ j ], dp[ j - weight[ i ] ] + value[ i ]);

3. 初始化。只能确定含量是0的背包装下的价值是0,所以dp[0]=0。其他的不能确定,都初始化为0。

4. 遍历顺序。在上面说到:背包问题里,两个for循环的先后循序是非常有讲究的。在这里也体现出来。二维的时候,先背包或者先物品都可以,但是一维的时候,只能先物品再背包,而且背包还得倒序遍历

为什么背包是倒序遍历?倒序遍历是为了保证物品i只被放入一次。比如上面的例题,物品0的重量weight[0] = 1,价值value[0] = 15。第一轮i=0:先算dp[1]=max(dp[1],dp[0]+15)=15,那么dp[2]=max(dp[2] , dp[1] + 15)=30,dp[2]就包含了2个物品0。肯定是错的。那么考虑反过来,先算dp[4]的话,先算dp[4]=max(dp[4],dp[3]+15)=15,dp[3]=max(dp[3],dp[2]+15)=15,没有重复包含。所以只能倒序遍历。所以倒序遍历的原因是,本质上还是一个对二维数组的遍历,只不过第二行的覆盖第一行,第三行的覆盖第二行……并且右下角的值依赖上一层左上角的值,因此需要保证左边的值仍然是上一层的,从右向左覆盖。从左到右覆盖左边的值就是这一层更新过的了。

为什么只能先物品再背包?还是那句话:一维遍历本质上还是一个对二维数组的遍历,右下角的值依赖上一层左上角的值,所以需要保证左边的值仍然是上一层的,结合上面的背包倒序遍历,想象这个过程中,dp数组倒序遍历一轮就是更新了之前二维数组的一行,然后下一轮就是更新二维数组的下一行,这样左边的值仍然是上一层的。

如下图。既然没有了i,那么进行第二轮的j=4,j=3的时候,之前一轮的这两个值就会被覆盖,只有以“先物品再背包背包倒序遍历”这个顺序来才能使得dp[j]和二维的dp[i-1][j]是一样的效果,我需要用到的是前一轮的值,那么不能先更新前一轮的值,而是要从后往前更新。所以除了这个情况之外的,都会覆盖原来左上角的值,是不对的。

二维数组的时候,本来就是由上一层的dp[i-1]计算得到的,所以上一层的值直接能拿来用不会被覆盖,所以先物品先背包都可以。

背包循环里面,j<nums[i]的dp[j]保持以前的值,和二维的dp[i][j]=dp[i-1][j]对应,所以是判断条件。

5.打印。

代码如下:

void maxValue(){
    int m,begweight;//M 代表物品的种类数,begweight是背包容量
    cin>>m>>begweight;
    vector<int> weight(m);
    vector<int> value(m);
    for(int i=0;i<m;++i){
        cin>>weight[i];
    }
    for(int i=0;i<m;++i){
        cin>>value[i];
    }
    vector<int> dp(begweight+1,0);
    //初始化
    dp[0]=0;
    //递推,特别注意物品背包的顺序和背包循环内的顺序
    for(int i=0;i<m;++i){
        for(int j=begweight;j>=weight[i];--j){
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<< dp[begweight] << endl;
}

● 416. 分割等和子集

只要找到一个子集,这个子集的和是sum / 2即可,sum是n个数之和。是奇数可以直接返回false。

怎么转换成01背包问题?背包含量begweight是sum/2,n件物品——n个数;重量weight数组——n个数的值;价值value数组——n个数的值;只要背包最后在n个数中找到的子集的和(最大价值)是sum/2,返回true。

代码如下:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int a:nums)sum+=a;
        if(sum%2==1)return false;
        int begweight=sum/2;    //背包容量
        vector<int> dp(begweight+1,0);
        for(int i=0;i<nums.size();++i){ //注意nums.size()和begweight别弄混
        //j<nums[i]的dp[j]保持以前的值,和二维的dp[i][j]=dp[i-1][j]对应
            for(int j=begweight;j>=nums[i];--j){    
                dp[j]=max(dp[j],dp[j-nums[i]]+ nums[i]);
            }
        }
        //最后结果等于begweight(即sum/2),找到
        if(dp[begweight]==begweight)return true;
        return false;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/411524.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C进阶】顺序表详解

文章目录 &#x1f4dd;线性表的概念&#x1f320; 顺序表&#x1f309;顺序表的概念 &#x1f320;声明--接口&#x1f309;启动&#x1f320;初始化&#x1f309;扩容&#x1f320;尾插&#x1f309; 打印&#x1f320;销毁&#x1f309; 尾删&#x1f320;头插&#x1f309;…

内存函数(C语言进阶)

目录 前言 1、memcpy 2、memmove 3、memcmp 4、memset 结语 前言 本篇介绍了C语言中的内存函数&#xff0c;内存函数&#xff0c;顾名思义就是处理内存的函数。 1、memcpy memcpy&#xff1a;内存拷贝函数。 相对于strcpy只能拷贝字符串来讲&#xff0c;memcpy能拷…

Mysql学习之事务日志undolog深入剖析

Undo log redo log 是事务持久性的保证&#xff0c;undo log是事务原子性的保证。在事务中更新数据的前置操作其实是要先写入一个undo log。 如何理解undo 日志&#xff1f; 事务需要保证原子性&#xff0c;也就是事务中的操作要么全部完成&#xff0c;要么什么也不做。但有时…

kitti数据显示

画出track_id publish_utils.py中 def publish_3dbox(box3d_pub, corners_3d_velos, types, track_ids):marker_array MarkerArray()for i, corners_3d_velo in enumerate(corners_3d_velos):marker Marker()marker.header.frame_id FRAME_IDmarker.header.stamp rospy.T…

kubernetes的网络flannel与caclio

flannel网络 跨主机通信的一个解决方案是Flannel&#xff0c;由CoreOS推出&#xff0c;支持3种实现&#xff1a;UDP、VXLAN、host-gw udp模式&#xff1a;使用设备flannel.0进行封包解包&#xff0c;不是内核原生支持&#xff0c;上下文切换较大&#xff0c;性能非常差 vxlan模…

golang学习3,golang 项目中配置gin的web框架

1.go 初始化 mod文件 go mod init gin-ranking 2.gin的crm框架 go get -u github.com/gin-gonic/gin 3.go.mod爆红解决

五种多目标优化算法(MOFA、NSWOA、MOJS、MOAHA、MOPSO)性能对比(提供MATLAB代码)

一、5种多目标优化算法简介 多目标优化算法是用于解决具有多个目标函数的优化问题的一类算法。其求解流程通常包括以下几个步骤&#xff1a; 1. 定义问题&#xff1a;首先需要明确问题的目标函数和约束条件。多目标优化问题通常涉及多个目标函数&#xff0c;这些目标函数可能…

LeetCode刷题---从中序与后序遍历序列构造二叉树

解题思路: 首先还是定义哈希表将中序遍历的数插入进去&#xff0c;方便后序查阅 创建递归方法buildTreeNew(中序遍历数组&#xff0c;后序遍历数组&#xff0c;左或右子树在中序遍历数组中的起始和终止节点索引&#xff0c;左或右子树在后序遍历数组中的起始和终止节点索引) 后…

ThreadLocal从使用到实现原理与源码详解

ThreadLocal概述 ThreadLocal是多线程中对于解决线程安全的一个操作类&#xff0c;它会为每个线程都分配一个独立的线程副本从而解决了变量并发访问冲突的问题。ThreadLocal 同时实现了线程内的资源共享。 案例&#xff1a;使用JDBC操作数据库时&#xff0c;会将每一个线程的…

数据库系统概论(超详解!!!) 第一节 绪论

1.四个基本概念 1.数据&#xff08;Data&#xff09; 数据&#xff08;Data&#xff09;是数据库中存储的基本对象 数据的定义&#xff1a;描述事物的符号记录 数据的种类&#xff1a;数字、文字、图形、图像、音频、视频、学生的档案记录等 数据的含义称为数据的语义&…

第三百六十七回

文章目录 1. 概念介绍2. 方法与细节2.1 获取方法2.2 使用细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何获取当前系统语言"相关的内容&#xff0c;本章回中将介绍如何获取时间戳.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章…

HCIA-Datacom实验指导手册:5.1 实验一:FTP SFTP TFTP 基础配置实验

HCIA-Datacom实验指导手册&#xff1a;5.1 实验一&#xff1a;FTP 基础配置实验 一、实验介绍&#xff1a;二、实验拓扑&#xff1a;三、实验目的&#xff1a;四、配置步骤&#xff1a;步骤 1 设备基础配置步骤 2 在 Router 上配置 FTP 和SFTP服务器功能及参数步骤 3 配置本地 …

MySQL数据库基础(十五):PyMySQL使用介绍

文章目录 PyMySQL使用介绍 一、为什么要学习PyMySQL 二、安装PyMySQL模块 三、PyMySQL的使用 1、导入 pymysql 包 2、创建连接对象 3、获取游标对象 4、pymysql完成数据的查询操作 5、pymysql完成对数据的增删改 PyMySQL使用介绍 提前安装MySQL数据库&#xff08;可以…

js里面有引用传递吗?

一&#xff1a;什么是引用传递 引用传递是相对于值传递的。那什么是值传递呢&#xff1f;值传递就是在传递过程中再复制一份&#xff0c;然后再赋值给变量&#xff0c;例如&#xff1a; let a 2; let b a;在这个代码中&#xff0c;let b a; 就是一个值传递&#xff0c;首先…

js中浏览器渲染原理

JavaScript&#xff08;JS&#xff09;是一种广泛使用的编程语言&#xff0c;特别是在Web开发中。在浏览器中&#xff0c;JS被用于实现动态网页效果、交互性和用户体验的提升。然而&#xff0c;要理解JS在浏览器中的工作原理&#xff0c;我们首先需要了解浏览器的渲染过程。 浏…

【回顾】蚂蚁链自研TEE技术全项通过国家金融科技认证中心认证

2022年3月&#xff0c;蚂蚁集团自研TEE技术&#xff08;HyperEnclave&#xff09;通过了北京国家金融科技认证中心认证&#xff0c;TEE功能&#xff08;CA与TA交互、数据存储、加密解密算法等&#xff09;、TEE安全&#xff08;硬件安全、系统软件层安全等&#xff09;47个项目…

【51单片机】红外遥控红外遥控电机调速(江科大)

1.红外遥控简介 红外遥控是利用红外光进行通信的设备,由红外LED将调制后的信号发出,由专用的红外接收头进行解调输出 通信方式:单工,异步 红外LED波长:940nm 通信协议标准:NEC标准 2.硬件电路 红外发送部分 IN高电平时&#xff0c;LED不亮&#xff0c;IN低电平时&…

这几个Python内置函数你都知道吗

divmod() divmod() 是一个 Python 内置函数&#xff0c;用于同时返回商和余数。它接受两个参数&#xff0c;第一个参数是被除数&#xff0c;第二个参数是除数&#xff0c;返回一个包含两个值的元组&#xff0c;第一个值是商&#xff0c;第二个值是余数。 示例用法如下&#…

Laravel03 路由到控制器与连接数据库

Laravel03 路由到控制器与连接数据库 1. 路由到控制器2. 连接数据库 1. 路由到控制器 如下图一些简单的逻辑处理可以放在web.php中&#xff0c;也就是路由的闭包函数里面。但是大的项目&#xff0c;我们肯定不能这么写。 为什么保证业务清晰好管理&#xff0c;都应该吧业务逻辑…

设计模式(三)建造者模式

相关文章设计模式系列 1.建造者模式简介 定义 建造者模式&#xff08;builder&#xff09;&#xff0c;将一个复杂对象的构建与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 简介 建造者模式&#xff08;builder&#xff09;是创建一个复杂对象的创建型…