【代码训练营】day44 | 完全背包理论 518. 零钱兑换 II 377. 组合总和 Ⅳ

news/2024/3/29 9:08:59/文章来源:https://blog.csdn.net/weixin_48494936/article/details/129243155

所用代码 java

完全背包

01背包物品只能使用一次 – 倒序遍历

for(i = 0; i < weight.length; i++){ 物品for (j = bagWeight; j >= weight[i]; j--){ 背包dp[j] = max(dp[j], dp[j-weight[i]] + value[i])}
}

完全背包物品可以使用无限次 – 正序遍历

for(i = 0; i < weight.length; i++){ 物品for (j = weight[i]; j <= bagWeight; j++){ 背包dp[j] = max(dp[j], dp[j-weight[i]] + value[i])}
}

完全背包for循环中可以颠倒,先遍历谁都可以

零钱兑换 II LeetCode 518

题目链接:零钱兑换 II LeetCode 518 - 中等

思路

  • dp[j]:装满背包j的情况有dp[j]种

  • 递推公式:dp[j] += dp[j-coins[i]]

  • 初始化:dp[0] = 1 如果等于0,后面累加就会一直是0, 空集也是一种方法

    • dp[1] += dp[0],1要从0得到结果然后继续累加
  • 遍历方向:coins[i] <= j <= amount

  • 打印dp

class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int i = 0; i < coins.length; i++) { // 物品for (int j = coins[i]; j <= amount; j++){ // 背包dp[j] += dp[j-coins[i]];
//                System.out.print("\tdp[j] = " + dp[j]);}
//            System.out.println();}return dp[amount];}
}

总结

先遍历物品,后遍历背包,保证了物品是从1、2、3开始的,不会有重复,也就是说这是一个组合数

若先遍历背包,再遍历物品,每次物品都是从1开始,就会有重复数,如1,2 2,1 但是这可以代表排列数

组合总和 Ⅳ leetCode 377

题目链接:组合总和 Ⅳ leetCode 377 - 中等

思路

  • dp[j] :和为j的情况有dp[j]种
  • 递推:dp[j] += dp[j-nums[i]]
  • 初始化:dp[0] = 1
  • 遍历顺序:先背包,后物品
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int j = 0; j <= target; j++) { // 背包for (int i = 0; i < nums.length; i++) { // 物品if (j >= nums[i]) dp[j] += dp[j-nums[i]];System.out.print("\tdp[j] = " +dp[j]);}System.out.println();}return dp[target];}
}

总结

背包为0可以装下物品 1 2 3 这其实是一个悖论,也可以认为是背包为0的可以装下无限大的东西。但是我认为把这个看成一个初始化无意义的值就行了,以防止出现后序累加的值一直为0。

dp数组的打印值

        dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 2   dp[j] = 2dp[j] = 2   dp[j] = 3   dp[j] = 4dp[j] = 4   dp[j] = 6   dp[j] = 7

若是觉得这值确实没必要,我们其实可以从j=1开始遍历,所打印的值就有助于对于dp数组的理解。

        dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 2   dp[j] = 2dp[j] = 2   dp[j] = 3   dp[j] = 4dp[j] = 4   dp[j] = 6   dp[j] = 7

所以,通过这两个题,我们可以明白:

  • 先遍历物品,再遍历背包:组合问题 - 无重复
  • 先遍历背包,再遍历物品:排列数 - 有重复(可排序)

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

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

相关文章

【C语言】自定义类型:结构体、枚举、联合

目录 1.结构体 1.1结构体类型 1.2结构体的自引用 1.3结构体的初始化 1.4结构体内存对齐 //对齐 //offsetof //修改默认对齐数 1.5结构体传参 2.位段 2.1位段的内存开辟 2.2位段的内存分配 3.枚举 4.联合&#xff08;共用体&#xff09; //判断大小端 1.结构体…

广泛运用在工业、轨道交通、监狱的ip对讲终端

ip网络对讲系统是不同于传统广播、调频寻址广播和数控广播的产品&#xff0c;它是基于IP数据网络&#xff0c;将音频信号经过数字编码以数据包形式按TCP\IP协议在局域网或广域网上传送&#xff0c;再由终端解码的纯数字化单向&#xff0c;双向及多向音频扩声系统。 本产品是新一…

2023前端二面经典手写面试题

实现一个call call做了什么: 将函数设为对象的属性执行&删除这个函数指定this到函数并传入给定参数执行函数如果不传入参数&#xff0c;默认指向为 window // 模拟 call bar.mycall(null); //实现一个call方法&#xff1a; Function.prototype.myCall function(context…

LLaMA-META发布单卡就能跑的大模型

2023年2月25日&#xff0c;Meta使用2048张A100 GPU&#xff0c;花费21天训练的Transformer大模型LLaMA开源了。 1.4T tokenstakes approximately 21 days 以下是觉得论文中重要的一些要点 1&#xff09;相对较小的模型也可以获得不错的性能 研究者发现在给定计算能力限制的情…

《高性能MySQL》读书笔记(下)

目录 Mysql查询性能的优化 慢查询基础 优化数据访问 是否向数据库请求了不需要的数据 查询了不需要的记录 多表联查中返回全部列 MySQL是否在扫描额外的记录 重写查询的方式 切分查询&#xff08;重点&#xff09; 分解连接查询&#xff08;重点&#xff09; MySQL如…

史上最全的大数据开发八股文【自己的吐血总结】

自我介绍 我本硕都是双非计算机专业&#xff0c;从研一下开始学习大数据开发的相关知识&#xff0c;从找实习到秋招&#xff0c;我投递过100公司&#xff0c;拿到过10的offer&#xff0c;包括滴滴、字节、蚂蚁、携程、蔚来、去哪儿等大厂&#xff08;岗位都是大数据开发&#…

算法练习(七)数据分类处理

一、数据分类处理 1、题目描述&#xff1a; 信息社会&#xff0c;有海量的数据需要分析处理&#xff0c;比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。采集输入大数据和分类规则&#xff0c;通过大数据分类处理程序&#xff0c;将大数据分类输出…

喜讯!华秋电子荣获第六届“蓝点奖”十佳分销商奖

2 月 25 日&#xff0c;由深圳市电子商会主办的2023 中国电子信息产业创新发展交流大会暨第六届蓝点奖颁奖盛典在深圳隆重举行。 图&#xff1a;华秋商城渠道总监杨阳&#xff08;右三&#xff09; 深圳市电子商会连续六年举办“蓝点奖”评选活动&#xff0c;旨在表彰对电子信…

高端电器新十年,求解「竞速突围」

竞争激烈的高端电器品牌们&#xff0c;平时王不见王&#xff0c;但也有例外。海尔、博西、海信、创维、方太、老板等等近乎中国电器行业所有一线品牌副总裁级别以上高层&#xff0c;2月22日都现身于上海&#xff0c;来参加一场由红星美凯龙攒起来的高端电器局&#xff0c;2023中…

能在软路由docker给部署搭建teamsperk服务器么?并且设置好ddns

参考链接(4条消息) 【个人学习总结】使用docker搭建Teamspeak服务器_blcurtain的博客-CSDN博客_teamspeak3 docker(⊙﹏⊙)哎呀&#xff0c;崩溃啦&#xff01; (tdeh.top)TeamSpeak服务器搭建与使用 - 缘梦の镇 (cmsboy.cn)Openwrt X86 docker运行甜糖-软路由,x86系统,openwrt…

虚拟数字人直播带货相比人工有哪些优势?

新经济时代的到来&#xff0c;彻底改变了传统的消费方式。虚拟数字人的出现&#xff0c;标志着新一波的消费升级到来。虚拟数字人直播带货&#xff0c;不仅降低了商家的带货成本&#xff0c;拉近了商家与消费者的距离&#xff0c;也给消费者带来全新的消费方式。 花西子虚拟形象…

如何查看Spring Boot各版本的变化

目录 1.版本 2.基础特性和使用 3.新增特性和Bug修复 1.版本 打开Spring官网&#xff0c;点进Spring Boot项目我们会发现在不同版本后面会跟着不同的标签&#xff1a; 这些标签对应不同的版本&#xff0c;其意思如下&#xff1a; GA正式版本&#xff0c;通常意味着该版本已…

k8s学习之路 | Day16 k8s 中的容器初探

文章目录容器镜像镜像名称镜像拉取策略私有仓库的拉取策略容器的环境变量和启动命令容器的环境变量容器的启动命令容器的生命周期钩子postStartpreStop容器的探针startupProbelivenessProbereadinessProbek8s 集群中最小的管理单元就是一个Pod&#xff0c;而Pod里面才是容器&am…

利用GPT-3 Fine-tunes训练专属语言模型

利用GPT-3 Fine-tunes训练专属语言模型 文章目录什么是模型微调&#xff08;fine-tuning&#xff09;&#xff1f;为什么需要模型微调&#xff1f;微调 vs 重新训练微调 vs 提示设计训练专属模型数据准备清洗数据构建模型微调模型评估模型部署模型总结什么是模型微调&#xff0…

JavaScript split()方法

JavaScript split()方法 目录JavaScript split()方法一、定义和用法二、语法三、参数值四、返回值五、更多实例5.1 省略分割参数5.2 使用limit参数5.3 使用一个字符作为分割符一、定义和用法 split() 方法用于把一个字符串分割成字符串数组。 二、语法 string.split(separat…

NCRE计算机等级考试Python真题(四)

第四套试题1、以下选项中&#xff0c;不属于需求分析阶段的任务是&#xff1a;A.需求规格说明书评审B.确定软件系统的性能需求C.确定软件系统的功能需求D.制定软件集成测试计划正确答案&#xff1a; D2、关于数据流图&#xff08;DFD&#xff09;的描述&#xff0c;以下选项中正…

RTMP的工作原理及优缺点

一.什么是RTMP&#xff1f;RTMP&#xff08;Real-Time Messaging Protocol&#xff0c;实时消息传输协议&#xff09;是一种用于低延迟、实时音视频和数据传输的双向互联网通信协议&#xff0c;由Macromedia&#xff08;后被Adobe收购&#xff09;开发。RTMP的工作原理是&#…

IP-GUARD控制台账户输入多次错误密码锁定后该如何解锁?

其他管理员账户给锁定了,暂时只能等其锁定时间到了才可以再次输入,默认是设置是锁定30min; 1、如果急需此账户查看,可以使用admin系统管理员账户登录控制台,在工具-账户中清除这个账户的密码,重新登录设置密码。

NIO与零拷贝

目录 一、零拷贝的基本介绍 二、传统IO数据读写的劣势 三、mmap优化 四、sendFile优化 五、 mmap 和 sendFile 的区别 六、零拷贝实战 6.1 传统IO 6.2 NIO中的零拷贝 6.3 运行结果 一、零拷贝的基本介绍 零拷贝是网络编程的关键&#xff0c;很多性能优化都离不开。 在…

【云原生kubernetes】k8s 常用调度策略使用详解

一、前言 通过之前的学习&#xff0c;我们了解到k8s集群中最小工作单位是pod&#xff0c;对于k8s集群来说&#xff0c;一个pod的完整生命周期是由一系列调度策略来控制&#xff0c;这些调度策略具体是怎么工作的呢&#xff1f;本文将详细讨论下这个问题。 二、k8s调度策略简介…