代码随想录训练营Day31:动态规划3:0-1背包

1.0-1背包基础

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大

1.1动态规划五部曲

  1. 确定dp数组以及下标的含义:dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。在后续的程序中都是默认背包的容量为i,物品的类别为j,保证统一。

2.确定递推公式

  • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以背包内的价值依然和前面相同。)
  • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值

所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化:需要根据具体的进行具体的初始化

4.那么问题来了,先遍历 物品还是先遍历背包重量呢?

其实都可以!! 但是先遍历物品更好理解。对于先遍历物品再遍历容量,简称为组合问题:这种情况下的遍历物品的顺序是一个固定的。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

先遍历背包,再遍历物品,也是可以的!(注意我这里使用的二维dp数组)。这种可以称之为排列问题可能会出现相同的结果但是不同的排列方式

例如这样:

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量for(int i = 1; i < weight.size(); i++) { // 遍历物品if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

5.举例:跳过,直接看下面的代码

2.416分割等和子集

第一种方法:动态规划的方法

理论分析:首先要分割成等和的子集,要满足的第一个条件就是其累加和能被2整除。

动态规划五部曲

1.dp[j]表示 背包总容量(所能装的总重量)是j,放进物品后,背的最大重量为dp[j]

2.递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);//分为填不添加这个数情况下的最大累加和。二维状态下是:dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]):i表示物品j表示容量

3.初始化:首先初始化的长度为target+1,因为我们只需要找到一个容量为sum一半的能够全部装满就代表还存在另外一部分。

4.确定遍历顺序:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!因为这样可以避免重复存放。可以看到上面的二维的递推公式,首先遍历的是物品,其次遍历的是容量,如果内部的容量是正序,那么会出现一个物品被多次使用。比如有1 2;2 3(重量 价值)的物品,这样的情况,正序遍历出现的结果就是dp数组为[2,4]而不是[2,3]的情况了。

class Solution {
public://动态规划的方法bool canPartition(vector<int>& nums) {int sum = 0;int n = nums.size();for(int i = 0;i<n;i++){sum += nums[i];}if(sum%2 ==1)return false;int target = sum/2;vector<int> dp(1+target,0);//生成一个dp数组for(int i = 0;i<n;i++){for(int j = target;j>=nums[i];j--){dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);//分加不加的情况下的最大值}}if(dp[target] == target)return true;return false;}
};

3.最后一块石头的重量

首先就是分析题意:我该如何让最后的石头的重量最小呢?就是通过将其分成两部分,两部分的差值越小那么对应的最后能够得到的重量也就越小。那么将其化成一个背包问题就是在求容量为target下能够存放的最大的重量为多少即0-1背包问题。

动态规划五部曲

1.dp[j]:容量为j时候的最大价值(重量)。

2.递推公式:dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);//在这个里面重量和价值都是用stones[i]来表示的,所以得到上述的公式,具体可以参考前面这一题的思路。

3.初始化:首先来说的话我们要用sum来确定总重量,然后确定dp数组的空间,应该生成的vector<int> dp(1+sum/2,0)的,但是按照题目给定了最多只有3000个,所以可以直接创建一个大的空间(1500>sum/2)。

4.循环的遍历方向:参照前面的分割等和子集。如果是一维的需要怎样的操作。

注意事项:最后返回的是 return sum - 2*dp[target];因为此时分成的两部分的重量分别为sum -dp[target]和dp[target],且必定是target>=dp[target]所以最后返回的是两者的差值即可。

class Solution {
public://dp数组,求得是能够背得的最大的重量,使用这种方法,巧妙的将碰撞的减法问题给反向思考为一个加法问题,最后相减来确定最小的重量int lastStoneWeightII(vector<int>& stones) {vector<int> dp(1501,0);int sum = accumulate(stones.begin(),stones.end(),0);//求累加和int target = sum/2;for(int i = 0; i<stones.size();i++){for(int j = target;j>=stones[i];j--){dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum - 2*dp[target];}
};

4.494目标和

结题思路看下面的注释部分。

动态规划五部曲:

1.dp[j]:代表容量为j的最大价值(和)的组合数。

2.递推公式:dp[j] += dp[j-nums[i]];组合类问题就是对应的多个的累加和。

3.初始化:在这个地方初始化需要初始化的长度是dp(avg+1);而不需要sum+1,因为left = avg;

4.遍历顺序:对于组合问题:应该先遍历背包再遍历容器。再就是遍历方向的问题:里面那个是从大往小的进行遍历,同前面一样是为了避免重复的情况。参考分割等和子集问题。

class Solution {
public://在这个里面,left代表的是正数的部分,right代表的是负数的部分//left + right = sum(定值)//left - right = target(定值)//left = (sum + target)/2;//所以此时两者的累加和一定能被2整除才行。//还需要考虑的就是sum>=abs(target)不然无法保证能够完成累加到指定的为止//所以此时dp[i]表示的就是累加和为i的个数//dp[j] += dp[j - nums[i]];//每一个nums[i]都对应的一个dp[j - nums[i]]种方法可以累加到这里int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size();int sum = accumulate(nums.begin(),nums.end(),0);//求和,后面那个应该是初始化的赋值if(abs(target)>sum)return 0;if((target+sum)%2==1) return 0;int avg = (target+sum)/2;vector<int> dp(avg+1);dp[0] = 1;for(int i = 0;i<nums.size();i++){for(int j = avg;j>= nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[avg];}
};

5.474一和零

1.dp[i][j]:i表示0的个数,j表示1的个数。dp[i][j]表示当前容量下的最大的个数。

2.递推公式: dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1);//其中dp[i-zeros][j-ones]表示的是dp[j-weight[i]]的意思,1:表示value[i].

3.初始化:默认开始的时候都是0。

4.遍历顺序:反序遍历保证不重复。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));//生成一个dp数组,用于确定有i个1,j个0for(auto str:strs){int zeros = 0;int ones = 0;for(auto st:str){if(st == '0'){zeros++;}else{ones++;}}for(int i = m;i >=zeros;i--){for(int j = n;j>=ones;j--){dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1);}}}return dp[m][n];}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【计算机网络】HTTP协议详解实战抓包分析教程

文章目录 1.HTTP简介2.HTTP报文的结构3.HTTP协议中空行的作用4.uri和url的区别5.HTTP请求5.1 HTTP请求方法5.2 HTTP请求报头 6.HTTP响应6.1 状态码 7.HTTP位于应用层(基于TCP)8.非持久和持久连接8.1 非持久连接8.2 持久连接 1.HTTP简介 HTTP&#xff08;Hypertext Transfer Pr…

爬虫入门经典(七) | 采集淘宝电场相关信息

大家好&#xff0c;我是不温卜火&#xff0c;昵称来源于成语—不温不火&#xff0c;本意是希望自己性情温和。 PS&#xff1a;由于现在越来越多的人未经本人同意直接爬取博主本人文章&#xff0c;博主在此特别声明&#xff1a;未经本人允许&#xff0c;禁止转载&#xff01;&a…

BakedSDF: Meshing Neural SDFs for Real-Time View Synthesis 论文阅读

&#xff08;水一篇博客&#xff09; 项目主页 BakedSDF: Meshing Neural SDFs for Real-Time View Synthesis 作者介绍 是 Mildenhall 和 Barron 参与的工作&#xff08;都是谷歌的&#xff09;&#xff0c;同时一作是 Lipman 的学生&#xff0c;VolSDF 的一作。本文引用…

VMware17.5与Ubuntu22.04虚拟机环境搭建

VMware17.5安装教程也有参考此链接 简介 Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的Unix工具软件、应用程序和网络协议。它支持32位和64位硬件。Linux继承了Unix以网络为核心的设…

【面试必看】MySQL部分

MySQL 1. 基础 1. 什么是关系型数据库&#xff1f; 一种建立在关系模型的基础上的数据库。关系模型表明了数据库中所存储的数据之间的联系&#xff08;一对一、一对多、多对多&#xff09;。各种表中&#xff08;比如用户表&#xff09;&#xff0c;表中的每一行就存放着一条…

ARM基于DWT实现硬件延时(GD32)

软件延时的缺点 软件延时的精度差&#xff0c;受系统主频影响&#xff0c;调教困难 硬件延时 DWT数据跟踪监视点单元硬件延时 硬件延时实现代码 delay.c #include <stdint.h> #include "gd32f30x.h"/** *****************************************************…

InfiniGate自研网关实现五

17.核心通信组件管理和处理服务映射 引入模块api-gateway-core 到 api-gateway-assist 中进行创建和使用&#xff0c;并拉取自注册中心的映射信息注册到本地的网关通信组件中。 第17节是在第15节的基础上继续完善服务发现的相关功能&#xff0c;把从注册中心拉取的网关映射信…

Qt qt5.3集成mqtt模块

参考 【Qt官方MQTT库的使用&#xff0c;附一个MqttClient例子】 - 叶小鹏 - 博客园 (cnblogs.com)MQTT&#xff1a;windows最简单搭建mqtt服务端及本地客户端测试_emqx-windows-4.3.6-CSDN博客MQTTX 下载 编译 我从Github下载的是Release v5.12.5 qt/qtmqtt (github.com)版…

达梦(DM) SQL基础操作

达梦DM SQL基础操作 用户与模式SQL基础操作查看表结构基础查询语句 在进行DM数据库SQL开发之前&#xff0c;首先需要了解一下DM数据库用户与模式的关系&#xff0c;因为这将直接影响到你后续对DM数据库的操作。那么DM数据库用户与模式的关系怎么理解呢&#xff1f; 用户与模式 …

【Linux系统编程】基本指令(二)

目录 1、mv指令 2、cat指令 输出重定向 ​编辑 追加重定向 输入重定向 3、more指令 4、less指令 5、head指令 6、tail指令 与时间相关的指令 7、date指令 8、cal指令 9、find指令 10、grep指令 11、zip/unzip指令 1、mv指令 mv文件是用来对文件或目录进行重命名…

vue3专栏项目 -- 五、权限管理(上)

一、登录部分 1、第一部分&#xff1a;获取token 前面我们主要是在获取数据上下功夫&#xff0c;到目前为止我们已经能获取首页和详情页的数据了&#xff0c;现在我们将数据转移到权限管理上来&#xff0c;也就是说我们要处理用户登录、注册等一系列的行为&#xff0c;在这部…

##20 实现图像风格迁移:使用PyTorch深入学习的艺术之旅

文章目录 前言项目概述准备阶段图像处理模型选择风格和内容特征提取风格迁移算法优化过程结果展示完整代码与实验项目结论参考文献 前言 图像风格迁移是一种使一幅图像呈现另一幅画作风格的技术&#xff0c;通过深度学习&#xff0c;我们能够捕捉到内容图像的结构信息和风格图…

react的多级路由定义

在写实验室项目的时候&#xff0c;有一个需求&#xff0c;在二级路由页面点击按钮&#xff0c;跳转到详情列表页面&#xff0c;同时三级路由不用在导航栏显示&#xff0c;效果图如下&#xff1a; 前期的尝试&#xff1a; 在route,js文件这样定义的&#xff1a; {path: music,…

【Linux】进程间通信(一)---- 匿名管道

【Linux】进程间通信&#xff08;一&#xff09;---- 匿名管道 一.序1什么是进程间通信2.进程间通信的标准3.为什么需要进程通信 二.匿名管道1.原理2.使用3.四种情况4.五个特点 一.序 1什么是进程间通信 进程间通信 通信我们大致知道是啥&#xff0c;就是互相传递信息 那进程…

pcdn边缘云常见sla有哪些?如何避免被白嫖

PCDN&#xff08;Point-to-Point Content Delivery Network&#xff09;边缘云常见的SLA&#xff08;Service Level Agreement&#xff09;规则包括高峰期离线、服务时间、重传延时、限速等。这些规则是为了保证服务质量和用户体验。下面将详细解释这些规则&#xff0c;并提供一…

win10共享文件夹到ubuntu22

win10共享文件夹 新建用户 新建用户、设置密码。避免共享给EveryOne&#xff0c;导致隐私问题。 点击左下角的开始菜单&#xff0c;选择“设置”&#xff08;WinI&#xff09;打开设置窗口。在设置窗口中&#xff0c;搜索或直接点击“账户”进入账户设置。在账户设置中&…

2024 年 11 款顶级Android数据恢复软件的主要功能

Android 设备上的数据丢失可能是一种令人痛苦的体验&#xff0c;通常会导致不可替代的信息瞬间消失。 可能会发生意外删除、系统崩溃或格式错误&#xff0c;关键数据的丢失可能会扰乱日常工作并影响您的工作效率。 幸运的是&#xff0c;技术进步带来了几种恢复解决方案&#…

Google IO 2024有哪些看点呢?

有了 24 小时前 OpenAI 用 GPT-4o 带来的炸场之后&#xff0c;今年的 Google I/O 还未开始&#xff0c;似乎就被架在了一个相当尴尬的地位&#xff0c;即使每个人都知道 Google 将发布足够多的新 AI 内容&#xff0c;但有了 GPT-4o 的珠玉在前&#xff0c;即使是 Google 也不得…

网易云如何改ip地址到另外城市

在数字化时代&#xff0c;网络音乐平台已经成为我们日常生活中不可或缺的一部分。然而&#xff0c;有时候我们可能会因为某些原因想要改变自己的IP地址&#xff0c;网易云音乐作为国内领先的音乐平台&#xff0c;其强大的功能和丰富的音乐资源吸引了大量用户。那么&#xff0c;…

详解 JuiceFS sync 新功能,选择性同步增强与多场景性能优化

JuiceFS sync 是一个强大的数据同步工具&#xff0c;支持在多种存储系统之间进行并发同步或迁移数据&#xff0c;包括对象存储、JuiceFS、NFS、HDFS、本地文件系统等。此外&#xff0c;该工具还提供了增量同步、模式匹配&#xff08;类似 Rsync&#xff09;、分布式同步等高级功…