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

算法训练营第四十四天|动态规划:完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

目录

  • 动态规划:完全背包理论基础
  • Leetcode518.零钱兑换II
  • Leetcode377. 组合总和 Ⅳ

动态规划:完全背包理论基础

文章链接:代码随想录
题目链接:卡码网:52. 携带研究材料

思路:完全背包问题,物品可以无限取,即不用考虑是否重复添加,在一维(滚动)数组解法上,将背包遍历变为正序。

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

Leetcode518.零钱兑换II

文章链接:代码随想录
题目链接:518.零钱兑换II

思路:完全背包求组合问题,改一下状态转移方程即可。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1);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];}
};

Leetcode377. 组合总和 Ⅳ

文章链接:代码随想录
题目链接:377. 组合总和 Ⅳ

思路:完全背包求排列问题,先遍历背包,再遍历物品,注意用例超界。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1);dp[0] = 1; for (int j = 0; 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];}
};

第四十四天打卡,加油!!!

相关文章:

算法训练营第四十四天|动态规划:完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

目录 动态规划&#xff1a;完全背包理论基础Leetcode518.零钱兑换IILeetcode377. 组合总和 Ⅳ 动态规划&#xff1a;完全背包理论基础 文章链接&#xff1a;代码随想录 题目链接&#xff1a;卡码网&#xff1a;52. 携带研究材料 思路&#xff1a;完全背包问题&#xff0c;物品可…...

探索计算机网络:应用层的魅力

在当今数字化时代&#xff0c;计算机网络已成为我们生活和工作中不可或缺的一部分。网络的每一层都扮演着独特而重要的角色&#xff0c;而应用层&#xff0c;作为网络模型中用户最直接接触的部分&#xff0c;其重要性不言而喻。这篇文章旨在深入探索应用层的核心概念、功能以及…...

MySQL 按日期流水号 条码 分布式流水号

有这样一个场景&#xff0c;有多台终端&#xff0c;要获取唯一的流水号&#xff0c;流水号格式是 日期0001形式&#xff0c;使用MySQL的存储过程全局锁实现这个需求。 以下是代码示例。 注&#xff1a;所有的终端连接到MySQL服务器获取流水号&#xff0c;如果获取到的是 “-1”…...

前端导出Excel文件,部分数字前面0消失处理办法

详细导出可以看之前的文章 js实现导出Excel文档_js 通过 接口 导出 xlsx 代码-CSDN博客 今天的问题是导出一些数据时&#xff0c;有些字段是前面带有0的字符串&#xff0c;而导出后再excel中就被识别成了数字 如图本来字符串前面的0 都没了 解决方案 1. 导出的时候在前面加单…...

零基础学Python网络爬虫案例实战 全流程详解 高级进阶篇

零基础学Python网络爬虫案例实战 全流程详解 入门与提高篇 零基础学Python网络爬虫案例实战 全流程详解 高级进阶篇 编辑推荐 本书讲解了Python爬虫技术的高级进阶知识&#xff0c;帮助有一定爬虫基础的读者进一步提高爬虫技术。本书详解了突破反爬机制的常用手段以及Scrapy和…...

第十二届“中关村青联杯”全国研究生数学建模竞赛-A题:水面舰艇编队防空和信息化战争评估模型(续)(附MATLAB代码实现)

目录 5.3.3 问题三的总结 5.4 问题四的模型建立与求解 5.4.1 问题分析 5.4.2 计算方位角和航向角...

bmp图像文件格式超详解

0 BMP简介 BMP(Bitmap-File)图形文件&#xff0c;又叫位图文件&#xff0c;是Windows采用的图形文件格式&#xff0c;在Windows环境下运行的所有图像处理软件都支持BMP图像文件格式。Windows系统内部各图像绘制操作都是以BMP为基础的。一个BMP文件由四部分组成&#xff1a; B…...

Unity Meta Quest 一体机开发(十三):【手势追踪】自定义交互事件 EventWrapper

文章目录 &#x1f4d5;教程说明&#x1f4d5;交互事件概述&#x1f4d5;自定义交互逻辑⭐方法一&#xff1a;Inspector 面板赋值⭐方法二&#xff1a;纯代码处理 此教程相关的详细教案&#xff0c;文档&#xff0c;思维导图和工程文件会放入 Spatial XR 社区。这是一个高质量…...

13、Redis高频面试题

1、项目中为什么用Redis 我们项目中之所以选择Redis&#xff0c;主要是因为Redis有下面这些优点&#xff1a; 操作速度快&#xff1a;Redis的数据都保存在内存中&#xff0c;相比于其它硬盘类的存储&#xff0c;速度要快很多数据类型丰富&#xff1a;Redis支持 string&#x…...

Koa学习笔记

1、npm 初始化 npm init -y生成 package.json 文件,记录项目的依赖2、git 初始化 git init生成 .git 隐藏文件夹,.git 的本地仓库创建 .gitignore 文件,添加不提交文件的名称3、创建 ReadMe.md 文件 记录项目笔记4、搭建项目 安装 Koa 框架npm install koa5、编写最基本的…...

HiDataPlus 3.3.2-005 搭建(个人的一点心得体会 x86 平台)

HDP 集群搭建 前置安装 yum -y install createrepo yum install -y lrzsz yum install -y wget yum install -y vim修改当前集群机器的主机名 hostnamectl set-hostname XXX​ 这里的 XXX 就是要设置的当前机器的主机名称。主机名称是集群唯一的&#xff0c;一定不要重复&am…...

【PHP】PHP实现与硬件串口交互,接收硬件发送的实时数据

一、前言 目的&#xff1a;借助虚拟串口软件&#xff08;VSPD&#xff09;模拟硬件串口发送数据&#xff0c;使用PHP语言实现接收硬件发送的数据。 我这里的需求是连接天平&#xff0c;把天平的称量数据实时的传送到PHP使用。 使用工具&#xff1a;vspd串口调试工具 使用语…...

HNU-数据库系统-作业

数据库系统-作业 计科210X 甘晴void 202108010XXX 第一章作业 10.09 1.(名词解释)试述数据、数据库、数据库管理系统、数据库系统的概念。 数据&#xff0c;是描述事物的符号记录。 数据库&#xff08;DB&#xff09;&#xff0c;是长期存储在计算机内、有组织、可共享的大量…...

Python基础知识:整理10 异常相关知识

1 异常的捕获 1.1 基础写法 """基本语法&#xff1a;try:可能发生错误的代码except:如果出现异常&#xff0c;将执行的代码""" try:fr open("D:/abc.txt", "r", encoding"utf-8") except:print("出现异常…...

golang并发安全-select

前面说了golang的channel&#xff0c; 今天我们看看golang select 是怎么实现的。 数据结构 type scase struct {c *hchan // chanelem unsafe.Pointer // 数据 } select 非默认的case 中都是处理channel 的 接受和发送&#xff0c;所有scase 结构体中c是用来存储…...

微软Visual Studio产品之Visual C++编程进阶——一维数组(画画版)

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;看到不少初学者在学习编程语言的过程中如此的痛苦&#xff0c;我决定做点什么&#xff0c;我小时候喜欢看小人书&#xff08;连环画&#xff09;&#xff0c;在那个没有电视、没有手机的年代&#xff0c;这是…...

Moonbeam生态项目分析 — — 下一代DeFi协议HydraDX

作者&#xff1a;David 概览 HydraDX是一个基于Substrate区块链框架构建的DeFi协议&#xff0c;旨在为波卡带来大量流动性。HydraDX的特色服务&#xff0c;HydraDX Omnipool&#xff0c;是一种创新的自动化做市商&#xff08;AMM&#xff09;&#xff0c;通过将所有资产组合在…...

Spark九:Spark调优之Shuffle调优

Spark shuffle调优方法 map端和reduce端缓存大小设置&#xff0c;reduce端重试次数和等待时间间隔&#xff0c;以及bypass设置 学习资料&#xff1a;https://mp.weixin.qq.com/s/caCk3mM5iXy0FaXCLkDwYQ 一、map和reduce端缓冲区大小 1.1 map端 在Spark任务运行过程中&…...

linux c多线程优先级

在 Linux 系统中&#xff0c;可以使用 pthread_setschedparam 函数来设置线程的优先级。该函数需要传入一个指向 pthread_t 类型的线程 ID&#xff0c;以及一个指向 struct sched_param 类型的结构体对象。struct sched_param 结构体包含了线程的优先级信息。 下面是一个示例代…...

Redis在项目开发中的应用

Spring Boot集成Redis构建博客应用 在这个示例中&#xff0c;我们将展示如何使用Spring Boot和Redis构建一个简单的博客应用&#xff0c;包括文章发布、点赞和评论功能。 1. 添加依赖 首先&#xff0c;我们需要在pom.xml文件中添加Spring Boot和Redis的依赖项。 <!-- Sp…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...