当前位置: 首页 > news >正文

盖子的c++小课堂——第二十三讲:背包问题

前言

又是一次漫长的更新(我真不是故意的aaaaaaaaaaaaaaa),先不多说了,直接给我~坐下~说错了说错了,直接开始~

背包问题----动态规划

背包问题(knapsack problem)

动态规划(dynamic programming)

01背包:可行性

对一个背包最多载重m斤,共有n件物品,第i件物品重量为w[i]。对每件物品可选择拿走或不拿。请问能否恰好拿到总重量为m斤?

 

 01决策:不选0,选1

凑数:可行性

目标凑出数字m,有n个数字可以使用,第i个数字为x[i]。对每一个数字最多可以选用1次。请问能否恰好凑出数字m?

 01决策:不选0,选1

简化问题

01背包:可行性

f[i][j]表示只用前i个数字能否凑出j

初始条件 

f[0][0]=1

状态转移方程

若j<x[i]——f[i][j]=f[i-1][j]

若j>=x[i]——f[i][j]=f[i-1][j]或f[i-1][j-x[i]]

01背包:3种问题

可行性判定问题

用n个物品能否恰好凑出m斤重量

方案计数问题

用n个物品能否恰好凑出m斤各种方案

最优化问题

用n个物品凑出不超过m斤时最多几斤

01背包

关于01背包,建议结合我的B站视频一起学习,相信会对你彻底理解背包问题有很大帮助!

带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili​www.bilibili.com/video/BV1cg411g7Y6​编辑icon-default.png?t=N7T8https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1cg411g7Y6带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili​www.bilibili.com/video/BV1BU4y177kY​编辑icon-default.png?t=N7T8https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1BU4y177kY

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

 

这是标准的背包问题,以至于很多混丝看了这个自然就会想到背包,甚至都不知道暴力的解法应该怎么解了。

这样其实是没有从底向上去思考,而是习惯性想到了背包,那么暴力的解法应该是怎么样的呢?

每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是O(2^n),这里的n表示物品数量。

 二维dp数组01背包

确定dp数组以及下标的含义

对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少?

要时刻记着这个dp数组的含义,下面的一些步骤都围绕这dp数组的含义进行的,如果哪里看懵了,就来回顾一下i代表什么,j又代表什么。

确定递推公式

再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。

那么可以有两个方向推出来dp[i][j],

  • 由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]
  • 由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]);

dp数组如何初始化

关于初始化,一定要和dp数组的定义吻合,否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。

dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。

代码如下:

for (int j = weight[0]; j <= bagWeight; j++) {dp[0][j] = value[0];
}

dp[0][j] 和 dp[i][0] 都已经初始化了,那么其他下标应该初始化多少呢?

dp[i][j]在推导的时候一定是取价值最大的数,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了,因为0就是最小的了,不会影响取最大价值的结果。

如果题目给的价值有负数,那么非0下标就要初始化为负无穷了。例如:一个物品的价值是-2,但对应的位置依然初始化为0,那么取最大值的时候,就会取0而不是-2了,所以要初始化为负无穷。

而背包问题的物品价值都是正整数,所以初始化为0,就可以了。

这样才能让dp数组在递归公式的过程中取最大的价值,而不是被初始值覆盖了。

最后初始化代码如下:

vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {dp[0][j] = value[0];
}

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

其实都可以!! 但是先遍历物品更好理解

那么我先给出先遍历物品,然后遍历背包重量的代码。

// 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]; // 这个是为了展现dp数组里元素的变化else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

 先遍历背包,再遍历物品,也是可以的

例如这样:

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

为什么也是可以的呢?

要理解递归的本质和递推的方向

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正左和正上两个方向)

其实背包问题里,两个for循环的先后循序是非常有讲究的,理解遍历顺序其实比理解推导公式难多了

总结

讲了这么多才刚刚把二维dp的01背包讲完,这里大家其实可以发现最简单的是推导公式了,推导公式估计看一遍就记下来了,但难就难在如何初始化和遍历顺序上

可能有的混丝并没有注意到初始化和遍历顺序的重要性,我们后面做力扣上背包面试题目的时候,大家就会感受出来了。

(这真是n年一度的大更新)

相关文章:

盖子的c++小课堂——第二十三讲:背包问题

前言 又是一次漫长的更新&#xff08;我真不是故意的aaaaaaaaaaaaaaa&#xff09;&#xff0c;先不多说了&#xff0c;直接给我~坐下~说错了说错了&#xff0c;直接开始~ 背包问题----动态规划 背包问题&#xff08;knapsack problem&#xff09; 动态规划&#xff08;dyna…...

k8s安装hostPath方式存储的PostgreSQL15

1.配置 PostgreSQL 的 ConfigMap cat > postgres-configmap.yaml << EOF apiVersion: v1 kind: ConfigMap metadata:name: postgres-configlabels:app: postgresnamespace: dev data:POSTGRES_DB: postgresdbPOSTGRES_USER: postgresadminPOSTGRES_PASSWORD: admin12…...

51单片机之按键和数码管

51单片机之按键和数码管 ✍前言&#xff1a;♐独立按键&#x1f600;独立按键的原理&#x1f600;软件实现按键控制LED灯的亮灭 ♐数码管&#x1f60a;数码管显示数字或者字母的原理&#x1f409;共阳极数码管&#x1f409;共阴极极数码管&#x1f409;4位1体数码管 &#x1f6…...

【Oracle】 - 数据库的实例、表空间、用户、表之间关系

Oracle是一种广泛使用的关系型数据库管理系统&#xff0c;它具有高性能、高可靠性、高安全性等特点。1Oracle数据库的结构和组成是一个复杂而又有趣的话题&#xff0c;本文将介绍Oracle数据库的四个基本概念&#xff1a;数据库、实例、表空间和用户&#xff0c;以及它们之间的关…...

ssm基于HTML5的交流论坛的设计与实现+vue论文

摘 要 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#xff0c;还是安全性&#xff0c;还是可操作性等各个方面来讲&#xff0c;遇到了互联网时代才发现能补上自古…...

JDBC*

*JDBC数据库连接步骤 1.将JDBC驱动的jar添加到项目的依赖中。 2.加载JDBC驱动 例如&#xff1a; Class.forName("com.mysql.jdbc.Driver"); 3.连接数据库 例如&#xff1a; Connection con DriverManager.getConnection(URL,us…...

Zookeeper注册中心实战

Java学习手册面试指南&#xff1a;https://javaxiaobear.cn Spring Cloud Zookeeper通过自动配置和绑定到 Spring 环境和其他 Spring 编程模型习惯用法&#xff0c;为 Spring Boot 应用程序提供Apache Zookeeper集成。通过一些简单的注释&#xff0c;您可以快速启用和配置应用…...

1-02VS的安装与测试

一、概述 对于一名C语言程序员而言&#xff0c;进行C语言程序的开发一般需要一个文本编辑器加上一个编译器就足够了。但为了方便起见&#xff0c;我们选择使用集成开发环境——Visual Studio&#xff08;简称VS&#xff09;。安装Visual Studio 下面讲一下如何安装VS&#xff0…...

ctfshow——PHP特性

文章目录 web 89web 90web 91web 92web 93web 94web 95web 96web 97web 98web 99web 100——优先级、eval()用法web 101——RefelctionClass反射类web 102——php伪协议、hex2bin()web103web 104——sha1绕过web 105 web 89 使用人工分配 ID 键的数值型数组绕过preg_match. 两个…...

K8S陈述式资源管理

陈述式 命令行&#xff1a;kubectl命令行工具 优点&#xff1a;90%以上的场景都可以满足&#xff0c;对增&#xff0c;删&#xff0c;查比较方便&#xff0c;对改不是很友好 缺点&#xff1a;命令比较冗长&#xff0c;复杂&#xff0c;难记 声明式 k8s当中的yaml文件来实现资…...

详解Python内置函数 !!!

内置函数就是Python给你提供的, 拿来直接用的函数&#xff0c;比如print&#xff0c;input等。 文章目录 前言 一、和数字相关 1. 数据类型 2. 进制转换 3. 数学运算 二、和数据结构相关 1. 序列 2. 数据集合 3. 相关内置函数 三、和数据结构相关 四、和迭代器生成器相关 五、字…...

使用Vue3 + Vite创建uni-app项目(Webstorm)

使用Vue3 Vite创建uni-app项目&#xff08;Webstorm&#xff09; 参考&#xff1a;前端VUE3Vite UniAPP-- 框架搭建_uniapp vite-CSDN博客 // 参考github.com的库&#xff1a;https://github.com/dcloudio/uni-preset-vue npx degit dcloudio/uni-preset-vue#vite-ts vite-vu…...

【js】js实现多个视频连续播放:

文章目录 一、效果&#xff1a;二、实现&#xff1a;三、案例&#xff1a; 一、效果&#xff1a; 二、实现&#xff1a; <!DOCTYPE html> <html> <head><title>Video Player</title><style>#progressBar { width: 800px;height: 20px;b…...

使用openssl 生成pfx格式证书时报错:unable to load certificates

问题现象包如下&#xff1a; 之前在centos上使用openssl部署证书服务器以及颁发证书的时候遇到的问题&#xff0c;在进行个人证书生成之后需要形成pfx格式证书&#xff0c;结果过程中报错了。网上类似资料比较少&#xff0c;做个记录。 生成pfx格式证书的命令&#xff1a; o…...

微信小程序 分享按钮 监听用户分享成功

代码 <view><button class"btnLq ed flex justify-center" open-type"share" click"getAward">点击分享</button> </view>export default {data(){return{shareMd:false,//分享埋点}},onShow(){//if(this.shareMd){uni.…...

数据结构-怀化学院期末题

题目&#xff1a; 利用希尔排序算法实现线性表的排序。希尔排序是根据给定的增量序列将线性表分隔成某个“增量”的记录组成一个子序例&#xff0c;在子序列中采用直接插入排序完成。 输入 第一行为元素个数n(1<n<1000)&#xff0c;第二行为n个元素值(整数)&#xff0c;即…...

跟cherno手搓游戏引擎【1】:配置与入口点

环境配置&#xff1a; 编译环境&#xff1a;VS2019 创建两个项目&#xff1a; 设置Sandbox为启动项&#xff1a; 设置sandbox的配置属性-常规-输出目录\中间目录为如下&#xff1a; 预处理定义&#xff1a;为了配置一些只有windows才能用的函数。 设置YOTOEngin&#xff08;我…...

25计算机专业考研经验贴之准备篇

Hello各位小伙伴&#xff0c;大家新年好&#xff01; 马上就要进入寒假假期了&#xff0c;25考研也该提上日程了。今天先跟大家分享一下大家在假期可以先做起来的准备工作。 【选择学校】 择校是个非常重要的内容&#xff0c;因为不同学校的考试内容是不一样的&#xff0c;有些…...

机器人相关知识

机器人学&#xff08;Robotics) 一些基础概念 位姿 位姿位置姿态 位姿的表示 刚体 刚性物体是一组粒子的集合&#xff0c;其中任意两个粒子之间的距离保持固定&#xff0c;不受物体运动或施加在物体上的力的影响。 “完全不可变形”的物体就是刚体。 刚体位置 刚性连杆 …...

八股文打卡day22——操作系统(5)

面试题&#xff1a;什么是死锁&#xff1f;如何避免死锁&#xff1f; 我的回答&#xff1a; 死锁是两个或者多个进程都占有各自的资源&#xff0c;然后都互相请求资源&#xff0c;导致互相都陷入了阻塞状态。 如何避免死锁呢&#xff1f; 首先&#xff0c;造成死锁有四个必要…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...