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

代码随想录算法训练营第44天 | 完全背包理论基础 518.零钱兑换II 377.组合总和 Ⅳ

完全背包理论基础

完全背包与01背包只相差在物品是无限取用的。因此和01背包相比第二层对背包容量的遍历应该是正序的,而且正因为这个正序,使得在纯完全背包问题中,背包容量和物品的遍历是可以倒过来的。

#include <bits/stdc++.h>
using namespace std;
int main() {int n, bagSize;cin >> n >> bagSize;vector<int> weight(n, 0);vector<int> value(n, 0);for(int i = 0; i < n; i++) {cin >> weight[i] >> value[i];}vector<int> dp(bagSize + 1, 0);for(int i = 0; i < n; i++) {for(int j = weight[i]; j <= bagSize; j++) {dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagSize] << endl;return 0;
}

零钱兑换II

Alt
这道题递推式和目标和那道题是一致的,都是解决装满背包的方法数目问题。重点在于遍历顺序,我们前面总结过对于纯完全背包问题,先遍历背包还是先遍历物品都是一样的。
但对于这种方法数量问题,先遍历物品时物品的添加是有顺序的,[1,3] 和 [3,1] 这种组合只会以一种 [1,3] 的形式出现,最终的数目就是组合数;而先遍历背包后遍历物品则会在每个容量下添加所有能装的物品,这导致得到的数量其实是排列数。

class Solution{
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for(int i = 0; i < coins.size(); i++) {for(int j = coins[i]; j <= amount; j++) {  // 这道题是组合数dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

组合总和IV

Alt
这道题对应了前面说的排列数目,需要先遍历背包,再遍历物品。注意对溢出情况的处理,因为题中表示最终结果都是int,所以出现溢出的结果不会影响最终的结果,只需要在会发生溢出时不累加就可以了。

class Solution{
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for(int j = 1; j <= target; j++) {for(int i = 0; i < nums.size(); i++) {if(j >= nums[i] && dp[j] <= INT_MAX - dp[j - nums[i]]) {dp[j] += dp[j - nums[i]];}}}return dp[target];}
};

相关文章:

代码随想录算法训练营第44天 | 完全背包理论基础 518.零钱兑换II 377.组合总和 Ⅳ

完全背包理论基础 完全背包与01背包只相差在物品是无限取用的。因此和01背包相比第二层对背包容量的遍历应该是正序的&#xff0c;而且正因为这个正序&#xff0c;使得在纯完全背包问题中&#xff0c;背包容量和物品的遍历是可以倒过来的。 #include <bits/stdc.h> usi…...

深度解析与推荐:主流Web前端开发框架

一、引言 在信息化社会中,Web前端开发的重要性日益凸显。作为连接用户与后台服务的关键桥梁,前端界面不仅直接影响用户体验,更是企业品牌形象、产品价值传递的重要载体。随着互联网技术的飞速发展,用户对于网站和应用的交互性、响应速度以及视觉效果等方面的要求越来越高,…...

【React】如何使antd禁用状态的表单输入组件响应点击事件?

最近遇到一个需求&#xff0c;需要在<Input.textarea>组件中&#xff0c;设置属性disabled为true&#xff0c;使textarea响应点击事件&#xff0c;但直接绑定onClick并不会在禁用状态下被响应。 解决方法1 之后尝试了很多方法&#xff0c;比如设置csspointer-events:no…...

Apache Flink

前言 最近在学习室内融合定位服务架构&#xff0c;业务架构上&#xff0c;涵盖了数据采集、处理、状态管理、实时计算和告警等多个方面&#xff0c;但有些问题&#xff1a;这套系统中包含了大量的有状态计算&#xff0c;目前是通过自设计内存对象进行管理&#xff0c;并利用Re…...

SpringMVC速成(一)

文章目录 SpringMVC速成&#xff08;一&#xff09;1.SpringMVC概述2.SpringMVC入门案例2.1 需求分析2.2 案例制作步骤1:创建Maven项目步骤2:补全目录结构步骤3:导入jar包步骤4:创建配置类步骤5:创建Controller类步骤6:使用配置类替换web.xml步骤7:配置Tomcat环境步骤8:启动运行…...

通过nginx学习linux进程名的修改

目录 1. 缘起2. 背景知识3. 源码分析3.1 准备工作3.2 设置进程名字 1. 缘起 在运行nginx的时候&#xff0c;用ps查看nginx的进程信息&#xff0c;可能的输出如下&#xff1a; root 42169 3105 0 16:51 ? 00:00:00 nginx: master process ./objs/nginx root …...

【PyTorch】实现迁移学习框架DANN

文章目录 前言代码实现1、导入数据库关于torch.manual_seed(1)2、参数设置3、数据导入4、定义训练函数4.1 nn.CrossEntropyLoss()4.2 .detach()4.3 .size VS .shape4.4 .to(DEVICE)4.5 .max()4.6 optimizer.zero_grad()4.7 len(data...

thinkphp6入门(18)-- 中间件中除了handle函数,还可以有其它函数吗

在ThinkPHP 6的中间件中&#xff0c;除了 handle 方法外&#xff0c;还可以定义其他方法。这些额外的方法可以用于执行中间件中的不同逻辑&#xff0c;但是只有 handle 方法是中间件的入口点&#xff0c;其他方法则需要在 handle 方法中手动调用。 (图片来自https://www.cnblog…...

Java stream 流的基本使用

Java stream 的基本使用 package com.zhong.streamdemo.usestreamdemo;import jdk.jfr.DataAmount; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.util.ArrayList; import java.util.Comparator; import java.util.Li…...

C++面向对象 Part 2

文章目录 类六个默认存在的成员函数构造函数&#xff1a;析构函数&#xff1a;拷贝构造函数:拷贝构造详解及细节&#xff1a; 赋值运算符重载;取地址及const取地址操作符重载const修饰的含义&#xff1a; 类六个默认存在的成员函数 构造函数 析构函数 拷贝构造函数 赋值运算…...

海外云手机的核心优势

随着5G时代的到来&#xff0c;云计算产业正处于高速发展的时期&#xff0c;为海外云手机的问世创造了一个可信任的背景。在资源有限且需求不断增加的时代&#xff0c;将硬件设备集中在云端&#xff0c;降低个人用户的硬件消耗&#xff0c;同时提升性能&#xff0c;这一点单单就…...

CDN相关和HTTP代理

CDN相关和HTTP代理 参考&#xff1a; 《透视 HTTP 协议》——chrono 把这两个放在一起是因为容易搞混&#xff0c;我一开始总以为CDN就是HTTP代理&#xff0c;但是看了极客时间里透视HTTP协议的讲解&#xff0c;感觉又不仅于此&#xff0c;于是专门写下来。 先说结论&#xf…...

STM32的ADC电压采集

时间记录&#xff1a;2024/2/9 一、ADC相关知识点 &#xff08;1&#xff09;STM32的ADC时钟不要超过14MHz&#xff0c;不然结果的准确率将下降 &#xff08;2&#xff09;ADC分为规则组和注入组&#xff0c;规则组相当于正常运行的程序&#xff0c;注入组相当于中断可以打断…...

基于麻雀优化算法优化XGBoost参数的优化控制策略

目录 一、背景 二、算法流程图 三、附录 一、背景 为提高极端梯度提升&#xff08;Extreme Gradient Boosting, XGBoost&#xff09;集成算法在时间预测、信贷风险预测、工件参数预测、故障诊断预测等方面中的准确性&#xff0c;研究者提出了一种改进的麻雀算法&#xff08;…...

Python爬虫——请求库安装

目录 1.打开Anaconda Prompt 创建环境2.安装resuests3.验证是否安装成功4.安装Selenium5.安装ChromeDriver5.1获取chrom的版本5.1.1点击浏览器右上三个点5.1.2点击设置5.1.3下拉菜单&#xff0c;点击最后关于Chrome&#xff0c;获得其版本 5.2 打开网址 [chromedriver](https:/…...

瑞芯微推理RKNN使用

参考资料 toolkit2 官网资料 野火实践指南 Ubuntu22.04实践 安装toolkit2 安装命令pip3 install -r xxx/packages/requirements_cp310-1.6.0.txt pip3 install xxx/packages/rknn_toolkit2-1.6.081f21f4d-cp310-cp310-linux_x86_64.whl注意加上 -i xxx 可能会造成下载tf-es…...

动漫风博客介绍页面源码

动漫风博客介绍页面源码&#xff0c;HTML源码&#xff0c;图片背景有淡入切换特效 蓝奏云&#xff1a;https://wfr.lanzout.com/iIDZu1nrmjve...

网络的基本概念和socket编程

网络的基本概念 1.协议1.1 协议的基本概念1.2 常见的协议 2.分层模型2.1网络七层OSI 7层模型&#xff1a;物数网传会表应(口诀)2.2TCP/IP模型2.3数据通信的过程2.4网络的设计模式2.5以太网帧的格式 3.SOCKET编程3.1网络字节序3.2 相关结构体和函数3.3 代码实现 1.协议 1.1 协议…...

探索C语言的内存魔法:动态内存管理解析

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C语言学习 贝蒂的主页&#xff1a;Betty‘s blog 1. 静态开辟内存 通过前面的学习&#xff0c;我们已经掌握了两种开辟内存的方…...

2023年全国职业院校技能大赛软件测试赛题第3套

2023年全国职业院校技能大赛 软件测试赛题第3套 赛项名称&#xff1a; 软件测试 英文名称&#xff1a; Software Testing 赛项编号&#xff1a; GZ034 归属产业&#xff1a; 电子与信息大类 …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...