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

代码随想录算法训练营第38天—动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ

完全背包

视频讲解:https://www.bilibili.com/video/BV1uK411o7c9
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

  • 题目描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品可以重复使用,求解怎么装背包里物品价值总和最大。
  • 解法大体和01背包的解法相同,以下以一维数组解法为例,其和01背包的解法主要有两点不同:
    • 一是内层for循环从逆向遍历改为正向遍历,因为完全背包里的每个物品是可以多次放入背包中的
    • 二是对于纯完全背包问题,内外层for循环是可以颠倒的,也就是说先遍历物品和先遍历背包容量都可以,其中为什么先遍历背包容量也可以呢?这样不会导致过程中某些dp[j]依赖于了下一个物品的dp[j]吗?其实是没关系的,无论是否依赖了下一个物品,我们最终得到的最后的那个结果值都不会变,也就是说过程中即便发生了变化,结果仍然是正确的。但从理论上来讲,其实还是应该先遍历物品,这样每一步都是正确的,不会产生困惑
      • 而对于完全背包应用类题目里的求装满背包有多少种情况的问题,内外层循环的顺序有如下讲究
        • 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
        • 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
  • 滚动数组(一维数组解法)
    • 动规五部曲
      • 一维dp数组dp[j]
        • 其中j代表背包的容量,dp值代表对应的最大价值
      • 递推公式
        • 当前 j 对应的最大价值为 装第i个物品不装第i个物品 两种情况里的较大值
        • 其中装第i个物品对应的dp值为dp[j - weight[i]] + value[i],weight[i]表示第i个物品的重量,value[i]代表第i个物品的价值
        • 不装第i个物品对应的dp值为dp[j]
        • dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
      • 一维dp数组的初始化
        • 全部初始化为0即可
      • 遍历顺序
        • 对于纯完全背包类问题,内外层for循环可以互相颠倒,但是二者的遍历顺序均是从前往后
      • 无需打印
    • 代码书写问题
# 一维数组解法
# m种物品,背包容量为n,每个物品的重量和价值分别保存在weight和value里
dp = [0] * (n + 1)
for i in range(1, m):for j in range(1, n + 1):if (j - weight[i]) >= 0:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[-1])

*518. 零钱兑换 II

视频讲解:https://www.bilibili.com/video/BV1KM411k75j
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html

  • 考点
    • 动态规划
    • 完全背包
    • 组合和排列(下一道题就是排列问题)
  • 我的思路
    • 思路就是给一个背包和给多个物品,问装满背包有多少种组合(每个物品可以重复拿取)
  • 视频讲解关键点总结
    • 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
      • 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
      • 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
  • 我的思路的问题
  • 代码书写问题
  • 可执行代码
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for i in range(len(coins)):for j in range(1, amount + 1):if j >= coins[i]:dp[j] += dp[j - coins[i]]return dp[-1]

377. 组合总和 Ⅳ

视频讲解:https://www.bilibili.com/video/BV1V14y1n7B6
https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html

  • 考点
    • 动态规划
    • 完全背包
    • 组合和排列
  • 我的思路
    • 思路就是给一个背包和给多个物品,问装满背包有多少种排列(每个物品可以重复拿取)
  • 视频讲解关键点总结
    • 我的思路没有问题,需要注意的是,不同的内外循环顺序会带来不同的结果,一种计算的是组合数,一种计算的是排列数(相同的元素,不同的顺序也视为不同)
      • 先遍历物品,再遍历背包容量,得到的结果是组合数——因为此时在不同种背包容量的情况里,都是先放进物品1再放进物品2,不会出现先放2再放1的情况,此时得到的组合之间不会出现顺序不同、元素相同的情况
      • 先遍历背包容量,再遍历物品,得到的结果是排列数——因为此时在背包容量递增的过程中,物品1和物品2放入的先后顺序不一定,可能先放了1也可能先放了2,因此集合之间会出现顺序不同、元素相同的情况,也就是得到的结果是排列数
  • 我的思路的问题
  • 代码书写问题
  • 可执行代码
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target + 1)dp[0] = 1for j in range(1, target + 1):for i in range(len(nums)):if j >= nums[i]:dp[j] += dp[j - nums[i]]return dp[-1]

相关文章:

代码随想录算法训练营第38天—动态规划06 | ● 完全背包 ● *518. 零钱兑换 II ● 377. 组合总和 Ⅳ

完全背包 视频讲解:https://www.bilibili.com/video/BV1uK411o7c9 https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html 题目描述:有n件物品和一个最多能…...

C语言每日一题(63)复写零

题目链接 力扣网 1089 复写零 题目描述 给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不…...

ElasticSearch聚合查询

数据准备 索引创建 PUT product {"mappings": {"properties": {"createtime": {"type": "date"},"desc": {"type": "text","fields": {"keyword": {"type": …...

【毕设级项目】基于AI技术的多功能消防机器人(完整工程资料源码)

基于AI技术的多功能消防机器人演示效果 竞赛-基于AI技术的多功能消防机器人视频演示 前言: 随着“自动化、智能化”成为数字时代发展的关键词,机器人逐步成为社会经济发展的重要主体之一,“机器换人”成为发展的全新趋势和时代潮流。在可预见…...

【一】【设计模式】类关系UML图

1. 继承(Generalization) 继承是对象间的一种层次关系,允许子类继承并扩展父类的功能。 UML线:带有空心箭头的直线,箭头指向基类(父类)。 class Parent {public void parentMethod() {System.…...

【DevOps基础篇】容器化架构基础设施监控方案

【DevOps基础篇】容器化架构基础设施监控方案 目录 【DevOps基础篇】容器化架构基础设施监控方案要监视什么不同监控系统方案比较1. Datadog2. Prometheus3. ELK(Elasticsearch、Logstash、Kibana)4. Sysdig5. 自行打造!如何选择总结推荐超级课程: Docker快速入门到精通 当…...

【QT】文件流操作(QTextStream/QDataStream)

文本流/数据流&#xff08;二级制格式&#xff09; 文本流 &#xff08;依赖平台&#xff0c;不同平台可能乱码&#xff09;涉及文件编码 #include <QTextStream>操作的都是基础数据类型&#xff1a;int float string //Image Qpoint QRect就不可以操作 需要下面的 …...

CentOS 7 devtoolset编译addressSanitizer版本失败的问题解决

在我的一个Cent OS7开发环境中&#xff0c;按https://yeyongjin.blog.csdn.net/article/details/134178420的方法升级GCC版本到8.3.1。 这两天&#xff0c;要用Google的addressSanitizer检验内存问题&#xff0c;加上编译参数后&#xff0c;却发现编译不通过。configure时直接退…...

ubuntu2004桌面系统英伟达显卡驱动安装方法

#如何查看显卡型号 lspci | grep -i vga#----output------ 01:00.0 VGA compatible controller: NVIDIA Corporation Device 1f06 (rev a1)根据 Device 后的 值 进入网站查询 pci-ids.ucw.cz/mods/PC/10de?actionhelp?helppci #根据显卡型号&#xff0c;下载对应系统的驱动…...

Java通过Excel批量上传数据!!!

一、首先在前端写一个上传功能。 <template><!-- 文件上传 --><el-upload class"upload-demo" drag action"" :on-change"onChange" :auto-upload"false"><el-icon class"el-icon--upload"><up…...

【PyQT/Pysider】控件背景渐变

默认渐变配色说明 background-color: qlineargradient(spread:pad, x1:0, y1:0, x2:1, y2:0, stop:0 rgba(255, 178, 102, 255), stop:0.55 rgba(235, 148, 61, 255), stop:0.98 rgba(0, 0, 0, 255), stop:1 rgba(0, 0, 0, 0));这段样式表使用了qlineargradient函数来创建…...

ChatGPT-4 VS 文心一言4.0

在线体验 地址&#xff08;含 gpt 3.5 / 4.0&#xff0c;文心 3.5 / 4.0&#xff09;&#xff1a;https://chat.tool4j.com 点击访问 文心一言和ChatGPT-4都是非常强大的自然语言处理模型&#xff0c;它们都能够在对话系统和其他NLP应用中发挥巨大的作用。然而&#xff0c;它们…...

MYSQL------从概述到DQL

数据库&#xff08;数据管理&#xff0c;数据存储的仓库&#xff09; 数据库管理系统&#xff08;操纵和管理数据库的大型软件&#xff09; SQL是操作关系型的编程语言&#xff0c;是一套标准 MySQL下载安装完成以后&#xff0c;可以进行启动和停止操作&#xff0c;对于启动和停…...

MATLAB算法实战应用案例精讲-【图像处理】图像识别(基础篇)(二)

目录 数字图像处理基本知识 传统图像处理方法进行瑕疵检测 传统算法方向的选择...

Leetcode 3.12

leetcode hot 100 链表1.两两交换链表中的节点2.随机链表的复制3.排序链表 链表 1.两两交换链表中的节点 两两交换链表中的节点 1.必须要设置一个dummy (temp) 结点2.保存第二个节点3.先让第一个节点指向第三个节点4.再让第二个节点指向第一个节点5.最后让dummy指向第二个节点…...

【天池课堂】零基础入门数据挖掘-课程汇总

写在前面&#xff1a; 如果你现在很迷茫&#xff0c;但是又对数据挖掘感兴趣&#xff0c;建议先看看以下两个视频直播&#xff0c;两位大佬亲身讲述自己和数据挖掘的前世今生。 《如何入门数据挖掘竞赛》 鱼遇雨欲语与余。天池明星选手&#xff0c;武汉大学硕士&#xff0c;天…...

表单进阶(3)-上传文件和隐藏字段

上传文件&#xff1a;<input type"file"> 隐藏字段&#xff1a;<input type"hidden" name"" id"" value"带给后端的信息"> 禁用disabled&#xff1a;<button disabled"disabled">注册</bu…...

LLM(大语言模型)常用评测指标-MAP@R

MAPR (Mean Average Precision at R) 是一种用于评估信息检索系统或排序模型效果的评价指标。它特别适用于那些返回一组相关结果的情况&#xff0c;例如搜索引擎或推荐系统。这里的“R”代表返回的相关结果的数量。MAPR 考虑了结果的排名和相关性两个因素。 计算方法 计算平…...

腾讯面经学习笔记

&#x1f496; 前言 &#x1f469;‍&#x1f3eb; 参考地址 &#x1f496; 操作系统 1. 进程和线程的区别 本质区别 进程是操作系统资源分配的基本单位线程是任务调度和执行的基本单位 开销方面 每个进程都有独立的代码和数据空间&#xff08;程序上下文&#xff09;&#…...

北京某中厂凉经

3月12号 大二想着找一份暑假面试&#xff0c;然后就海投。北京某上市公司给了面试&#xff0c;这也是我的第一个面试&#xff0c;听面试官最后的话大概是挂了。 大概回忆一下当时面试的部分内容吧&#xff0c;虽然已经过去一两小时的&#xff0c;而且我属于那种一面完就忘的差…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...