算法日记 30 day 动态规划(背包问题)

今天是动态规划的另一个大类,背包问题。

背包问题的分类

这张图中涵盖了我们能遇到的绝大部分背包问题。

首先是01背包问题

01背包问题

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

        对于01背包问题的解法,从dp数组的定义来看,可以写成二维数组和一维数组,接下来使用五部曲来分析分析这两种的写法区别。

这里先放一个例子,分析也都是通过这个例子来进行的:

背包最大重量为4。

物品为:

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

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

二维dp数组

        1.dp数组的含义

        因为背包问题涉及背包容量与物品两个维度,所以可以使用二维数组。那么对于dp[i][j]来说,这里假设i表示物品编号,j表示物品容量。

        那么对于dp数组的含义呢?

从图中可以看出来,dp数组的含义

dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。  

        2.递推公式

        dp[i][j]是由那些位置所决定的呢?

        假设对于dp[1][4],表示在0到1之间的物品任取放入背包容量4的背包中所能得到的最大价值。

求取 dp[1][4] 有两种情况:

  1. 放物品1
  2. 还是不放物品1

假设不放物品1,那么这个值应该是物品0放入背包4的最大价值,是15。

假设放入物品1,那么在放入物品1 之前需要确保背包的容量足够,那么才能放入物品1,并且需要价值最大,那么就需要保证出去物品1的容量后,背包的价值应改保持最大,此时表示为dp[i-1][j-weigth[i]]。那么再加上物品1的价值,就是放物品1的最大价值。 

综上来看:

        dp[i][j]=max(dp[i-1][j],dp[i-1][j-weig]th[i]+value[i])

        3.初始化

 

根据之前的分析,就能很清楚的看出来如何初始化。而其他的部分,按照dp的递推公式来看,初始化为什么其实都不重要,因为都会被覆盖掉。

        4.遍历顺序

        两个维度,物品与背包容量,其实先遍历谁都一样,结合dp公式和图来看,每一个dp都是有上一层和左上角位置所决定的,那么无论先遍历谁,这两个值都会提前被确定下来,所以不会影响dp[i][j]的值。

题目:携带研究材料(第六期模拟笔试)

46. 携带研究材料(第六期模拟笔试) (kamacoder.com)

题目描述

小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。 

小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。

输入描述

第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。

第二行包含 M 个正整数,代表每种研究材料的所占空间。 

第三行包含 M 个正整数,代表每种研究材料的价值。

输出描述

输出一个整数,代表小明能够携带的研究材料的最大价值。

 题目分析:

        标准的01背包问题。看代码

#include<iostream>
#include<string>
#include<vector>using namespace std;int main()
{int n, bagweight;// bagweight代表行李箱空间cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占空间vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}//dp数组定于vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化为0// j >= weight[0]的值就初始化为value[0]for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}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]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

一维dp数组(滚动数组)

        在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把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](一维数组,也可以理解是一个滚动数组)。

那么继续五部曲:

dp数组的含义,和二维数组的差不多

在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。

递推公式

 因为是将上一层的复制过来,所以不用考虑i的问题

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

因为是复制过来的,dp[j]这个位置本身是有值的,所以需要和自身比较。

初始化

dp[0]的位置很明显是0,那么其他位置呢?考虑到递推公式中需要和自身进行比较,为了不影响这个过程,初始化为0即可。

遍历顺序

这里先给出遍历的代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

可以看到,遍历背包容量的时候使用了倒序,这是因为为正序遍历会导致在求dp[j]时,将dp[j]的上一层提前复制,而在这一层会依靠上一次的结果,导致物品被多次放入。所以倒序遍历是为了保证物品i只被放入一次!

 那么他们之间的顺序是否可以像二维dp那样颠倒呢?

不可以。因为他是依赖于上一层的。

同样的题目,使用一维数组求解。

 题目:携带研究材料(第六期模拟笔试)

46. 携带研究材料(第六期模拟笔试) (kamacoder.com)

#include<iostream>
#include<string>
#include<vector>using namespace std;int main()
{// 读取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 创建一个动态规划数组dp,初始值为0vector<int> dp(N + 1, 0);for(int i=0;i<M;i++){for(int j=N;j>=costs[i];j--){dp[j]=max(dp[j],dp[j-costs[i]]+values[i]);}}// 输出dp[N],即在给定 N 行李空间可以携带的研究材料最大价值cout << dp[N] << endl;return 0;
}

 好了,看完01背包的基础,来看一看他的应用题

题目:分割等和子集

416. 分割等和子集 - 力扣(LeetCode)

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
题目分析:

首先,本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题,看看背包问题如何来解决。

只有确定了如下四点,才能把01背包问题套到本题上来。

  • 背包的体积为sum / 2
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

那么按照五部曲开始走。

dp[j]表示 背包总容量(所能装的总重量)是j,放进物品后,背的最大重量为dp[j]。那么如果背包容量为target, dp[target]就是装满 背包之后的重量,所以 当 dp[target] == target 的时候,背包就装满了。

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。

所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

public class Solution {public bool CanPartition(int[] nums) {int sum=0;//数组和for(int i=0;i<nums.Length;i++){sum+=nums[i];}if (sum % 2 == 1) return false;int target = sum / 2;int[] dp = new int[10001];//拆成2半,所有取和的一半即可for(int i=0;i<nums.Length;i++){for(int j=target;j>=nums[i];j--){dp[j]=Math.Max(dp[j],dp[j-nums[i]]+nums[i]);}}if (dp[target] == target)return true;return false;}
}

对于更详细的解析与其他语言的代码块,可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目:94

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何修复WordPress卡在维护模式

当你管理WordPress网站时&#xff0c;没有什么比看到它卡在维护模式更令人沮丧的了。特别是在你进行重要更新或期望大量流量的时候&#xff0c;这种情况会更加令人不安。 维护模式可能由许多因素引起&#xff0c;从简单的文件损坏到更复杂的插件冲突或存在的.maintenance文件。…

Oracle OCP认证考试考点详解082系列22

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 105. 第105题&#xff1a; 题目 解析及答案&#xff1a; 题目翻译&#xff1a; 关于Oracle数据库中的事务请选择两个正确的陈述&#xf…

目录背景缺少vscode右键打开选项

目录背景缺少vscode右键打开选项 1.打开右键管理 下载地址&#xff1a;https://wwyz.lanzoul.com/iZy9G2fl28uj 2.开始搜索框搜索vscode&#xff0c; 找到其源目录 3.目录背景里面&#xff0c; 加入vscode.exe 3.然后在目录背景下&#xff0c; 右键&#xff0c; code就可以打…

第三届航空航天与控制工程国际学术会议 (ICoACE 2024)

重要信息 会议官网&#xff1a;www.icoace.com 线下召开&#xff1a;2024年11月29日-12月1日 会议地点&#xff1a;陕西西安理工大学金花校区 &#xff08;西安市金花南路5号&#xff09; 大会简介 2024年第三届航空航天与控制工程国际学术会议&#xff08;ICoACE 2024&a…

【团购核销】抖音生活服务商家应用快速接入①——基础工作

文章目录 一、前言二、抖音开放平台&#xff08;服务商平台&#xff09;三、认证服务能力四、第三方生活服务商家应用五、APPID和AppSecret六、申请接口权限七、开发配置八、参考 一、前言 目的&#xff1a;将抖音团购核销的功能集成到我们自己开发的App和小程序中 名词解释技术…

十六.SpringCloudAlibaba极简入门-整合Grpc代替OpenFeign

前言 他来了他来了&#xff0c;停了快2个月了终于又开始更新文章啦&#xff0c;这次带来的绝对是干货&#xff01;&#xff01;&#xff01;。由于公司项目进行重构的时候考虑到&#xff0c;OpenFeign做为服务通信组件在高并发情况下有一定的性能瓶颈&#xff0c;所以将其替换…

MySQL库和表的操作

目录 一. 查看数据库 二. 创建数据库 三. 字符集和校验规则 四. 修改和删除数据库 4.1 数据库修改 4.2 数据库删除 五. 备份与恢复 5.1 备份 5.2 还原 5.3 注意事项 5.4 查看连接情况 六. 创建表 七. 查看表结构 八. 修改表 九. …

在Linux下配置gitee与Github的远程仓库

目录 前言 云服务器下载git 检测是否下载成功git Linux下配置gitee远程仓库 代码提交演示 git三板斧 Linux下配置Github远程仓库 最后的提醒 前言 那么本篇文章将是在&#xff0c;你已经创建了本地仓库的基础上&#xff0c;在Linux下配置gitee的远程仓库的步骤&#xff…

mini-lsm通关笔记Week2Day5

项目地址&#xff1a;https://github.com/skyzh/mini-lsm 个人实现地址&#xff1a;https://gitee.com/cnyuyang/mini-lsm Summary 在本章中&#xff0c;您将&#xff1a; 实现manifest文件的编解码。系统重启时从manifest文件中恢复。 要将测试用例复制到启动器代码中并运行…

ESP8266 STA模式TCP服务器 电脑手机网络调试助手

STA模式TCP服务器和手机电脑网络调试助手多连接

JMeter监听器与压测监控之Grafana

Grafana 是一个开源的度量分析和可视化套件&#xff0c;通常用于监控和观察系统和应用的性能。本文将指导你如何在 Kali Linux 上使用 Docker 来部署 Grafana 性能监控平台。 前提条件 Kali Linux&#xff1a;确保你已经安装了 Kali Linux。Docker&#xff1a;确保你的系统已…

基于AIRTEST和Jmeter、Postman的自动化测试框架

基于目前项目和团队技术升级&#xff0c;采用了UI自动化和接口自动化联动数据&#xff0c;进行相关测试活动&#xff0c;获得更好的测试质量和测试结果。

STM32设计防丢防摔智能行李箱-分享

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着科技的不断发展&#xff0c;嵌入式系统、物联网技术、智能设备…

全面解析:HTML页面的加载全过程(一)--输入URL地址,与服务器建立连接

用户输入URL地址&#xff0c;与服务器建立连接 用户在浏览器地址栏输入一个URL 浏览器开始执行以下三步操作操作&#xff1a;url解析、DNS查询、TCP连接 第一步&#xff1a;URL解析 什么是URL&#xff1f; URL(Uniform Resource Locator&#xff0c;统一资源定位符)是互联网…

window 中安装 php 环境

window 中安装 php 环境 一、准备二、下载三、安装四、测试 一、准备 安装前需要安装 Apache &#xff0c;可以查看这篇博客。 二、下载 先到这里下载 这里选择版本为“VS16 x64 Thread Safe”&#xff0c;这个版本不要选择线程安全的&#xff0c;我试过&#xff0c;会缺少文…

Android Studio启动模拟器显示超时

问题报错: Timed out after 300seconds waiting for emulator to come online. 解决方案&#xff1a;升级Android Emulator 情况二&#xff1a;Error while waiting for device:AVD Pixel_4a_API_32 is already running. If that is not the case, delete the files at E:\An…

基于企业微信客户端设计一个文件下载与预览系统

在企业内部沟通与协作中&#xff0c;文件分享和管理是不可或缺的一部分。企业微信&#xff08;WeCom&#xff09;作为一款广泛应用于企业的沟通工具&#xff0c;提供了丰富的API接口和功能&#xff0c;帮助企业进行高效的团队协作。然而&#xff0c;随着文件交换和协作的日益增…

【算法一周目】滑动窗口(1)

目录 长度最小的子数组 解题思路 代码实现 无重复字符的最大字串 解题思路 代码实现 最大连续1的个数l l l 解题思路 代码实现 将x减到0的最小操作数 解题思路 代码实现 长度最小的子数组 题目链接&#xff1a;209. 长度最小的子数组题目描述&#xff1a; 给定一个…

硬件工程师零基础入门:一.电子设计安全要点与欧姆定律

硬件工程师零基础入门:一.电子设计安全要点与欧姆定律 第一节 电子设计安全要点第二节 欧姆定律 第一节 电子设计安全要点 电路小白最好先买直流稳压电源&#xff08;将高压转成低压直流电&#xff09;使用&#xff0c;尽量不要使用市电。 1.尽量不要捏住电源两端。 正确做法&a…

【C++】踏上C++学习之旅(九):深入“类和对象“世界,掌握编程的黄金法则(四)(包含四大默认成员函数的练习以及const对象)

文章目录 前言1. 实现Date类的构造函数2. 实现Date类的拷贝构造函数3. 实现Date类的赋值运算符重载4. 实现各Date对象之间的比较接口5. 实现Date对象的加减接口6. const成员7. 取地址及const取地址操作符重载 前言 在我们前面学习到了"类和对象"的四大默认成员函数(…