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

代码随想录算法训练营第四十四天

sad的一天,明天开始上班,而且娃还行,媳妇儿状态不稳定,太难了也!!!

 完全背包

#include<vector>
#include<iostream>
using namespace::std;
int main(){int N;//种类int V;//空间cin >> N;cin >> V;vector<int>wi(N,0);vector<int>vi(N,0);for(int i = 0; i< N ;i++){cin >> wi[i];cin >> vi[i];}vector<int>dp(V+1,0);for(int i = 0;i < N;i++){for(int j = wi[i];j < V+1;j++){dp[j] = max(dp[j],dp[j - wi[i]]+vi[i]);}}std::cout << dp[V] << std::endl;return 0;
}

我理解的01背包和完全背包的核心代码区别:

01背包:物品在只能用一次,所以用背包空间去减当前物品的重量,然后去看是否需要用这个物品。

完全背包:用当前物品的重量去填满背包空间,然后用不同的物品去放。

 518. 零钱兑换 II  

随想录:这个递推公式大家应该不陌生了,我在讲解01背包题目的时候在这篇494. 目标和 (opens new window)中就讲解了,求装满背包有几种方法,公式都是:

dp[j] += dp[j - nums[i]];

class Solution {
public:int change(int amount, vector<int>& coins) {int N = coins.size();vector<int>dp(amount+1,0);dp[0] = 1;//和我昨天纠结那题一样,昨天用的是二维查表 494题for(int i = 0;i < N;i++){for(int j = coins[i];j < amount+1;j++){dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

377. 组合总和 Ⅳ  

因为存在不同顺序算不同的方法,所以for循环的内外循环需要变更,先遍历空间,再遍历物品。否则物品是有先后顺序的。

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

相关文章:

代码随想录算法训练营第四十四天

sad的一天&#xff0c;明天开始上班&#xff0c;而且娃还行&#xff0c;媳妇儿状态不稳定&#xff0c;太难了也&#xff01;&#xff01;&#xff01; 完全背包 #include<vector> #include<iostream> using namespace::std; int main(){int N;//种类int V;//空间ci…...

【3dmax笔记】027:配置修改器集、工具栏自定义与加载

文章目录 一、配置修改器集二、自定义工具栏三、加载工具栏 一、配置修改器集 可以把自己常用的修改命令放到右边框中的部分&#xff0c;便于自己的操作&#xff0c;省去了每次都要花半天时间找命令的尴尬。新建一个二维或者三维物体&#xff0c;点击修改面板&#xff0c;点击…...

Reactor模型详解

目录 1.概述 2.Single Reactor 3.muduo库的Multiple Reactors模型如下 1.概述 维基百科对Reactor模型的解释 The reactor design pattern is an event handling pattern for handling service requests delivered concurrently to a service handler by one or more inputs.…...

内存卡罢工,数据危机?别急,有救!

在日常生活和工作中&#xff0c;我们越来越依赖于各种电子设备来存储重要数据。其中&#xff0c;内存卡因其便携性和大容量而广受欢迎。然而&#xff0c;当内存卡突然损坏打不开时&#xff0c;我们该如何应对&#xff1f;本文将为您详细解析这一问题&#xff0c;并提供有效的解…...

python爬虫实战

import requests import json yesinput(输入页数&#xff1a;) yesint(yes)headers {"accept": "application/json, text/plain, */*","accept-language": "zh-CN,zh;q0.9","content-type": "application/json",…...

k8s 资源文件参数介绍

Kubernetes资源文件yaml参数介绍 yaml 介绍 yaml 是一个类似 XML、JSON 的标记性语言。它强调以数据为中心&#xff0c;并不是以标识语言为重点例如 SpringBoot 的配置文件 application.yml 也是一个 yaml 格式的文件 语法格式 通过缩进表示层级关系不能使用tab进行缩进&am…...

mac系统安装steam报错-解决办法

今天给虚拟机装了个苹果系统&#xff0c;然后想装个steam&#xff0c;从steam的官方下载安装steam_osx.dmg时&#xff0c;总是报“steam_osx已损坏&#xff0c;无法打开&#xff0c;请移动到废纸篓“。搜了一下找到了解决办法&#xff0c;这里记录一下。 双击steam_osx.dmg时&…...

这个簇状柱形图怎么添加百分比?

这个图表是excel默认的图表配色&#xff0c;有的人做出来都那个百分比&#xff0c;一起来做一个这样的图表。 1.插入图表 选中数据区域&#xff0c;点击 插入选项卡&#xff0c;在图表那一栏&#xff0c;点一下柱形图右侧那个倒三角&#xff0c;在弹邮对话框中&#xff0c;选…...

Tomact安装配置及使用(超详细)

文章目录 web相关知识概述web简介(了解)软件架构模式(掌握)BS&#xff1a;browser server 浏览器服务器CS&#xff1a;client server 客户端服务器 B/S和C/S通信模式特点(重要)web资源(理解)资源分类 URL请求路径(理解)作用介绍格式浏览器通过url访问服务器的过程 服务器(掌握)…...

web后端——netbeans ide +jsp+servlet开发学习总结

目录 jsp基础 netbeans开发工具问题HTTP Status 405 - HTTP method POST is not supported......netbeans 提示无法启动GlassFish Server 4.1.1:服务器未运行时, HTTP 或 HTTPS 监听程序端口已被占用404 问题netbeans中项目中有多个html文件,如何单独运行某个文件&#xff1f;n…...

使用request-try-notifyState流程实现UI控制与状态反馈的完整闭环

1. 前言 在Qt编程时&#xff0c;我们经常会在界面上添加一些按钮&#xff0c;当按钮被点击时&#xff0c;执行某段代码&#xff0c;例如显示一个对话框、关闭窗口&#xff0c;保存文件等等。 这种由UI控件触发某种信号&#xff0c;通过信号槽触发目的代码执行的场景非常多。这…...

屏蔽罩材质和厚度对屏蔽效能的影响

​ 一&#xff0e;屏蔽效能的影响因素 屏蔽效能的影响因素主要有两个方面&#xff1a;屏蔽材料的特性和厚度&#xff1b;如下图所示&#xff0c;电磁波经过不同媒介时&#xff0c;会在分界面形成反射&#xff0c;穿过界面的电磁波一部分被反射回去&#xff0c;这部分能量损失…...

Qt简单离线音乐播放器

有上传本地音乐文件&#xff0c;播放&#xff0c;暂停&#xff0c;拖拉进度条等功能的播放器。 mainwindow.cpp #include "mainwindow.h" #include "ui_mainwindow.h" #include <QMediaPlayer> #include <QFileDialog> #include <QTime&g…...

微信小程序常用的api

基础API&#xff1a; wx.request&#xff1a;用于发起网络请求&#xff0c;支持GET、POST等方式&#xff0c;是获取网络数据的主要手段。wx.showToast&#xff1a;显示消息提示框&#xff0c;通常用于向用户展示操作成功、失败或加载中等状态。wx.showModal&#xff1a;显示模态…...

iOS xib布局

1.多次启动发现启动图和截屏的图片不一致,设置launch storyboard 不能到顶部 https://blog.csdn.net/u011960171/article/details/104053696/ 2.multipiler是比例&#xff0c;需要控制顺序1.视图&#xff0c;2父视图&#xff0c;选择宽度比例&#xff0c;默认是1 3.Aspect R…...

UNI-APP_拨打电话权限如何去掉,访问文件权限关闭

uniapp上架过程中一直提示&#xff1a;允许“app名”拨打电话和管理通话吗&#xff1f; uniapp配置文件&#xff1a;manifest.json “permissionPhoneState” : {“request” : “none”//拨打电话权限关闭 }, “permissionExternalStorage” : {“request” : “none”//访…...

Git知识点汇总表格总结

Git应该是现在各个做开发公司使用最广泛的版本管理工具了&#xff0c;还有一些公司可能用的SVN&#xff0c;不过总体来说&#xff0c;Git绝对是主流&#xff0c;SVN是集中式版本管理&#xff0c;使用起来相对Git更简单&#xff0c;不过功能相对Git也略显简略&#xff0c;Git的优…...

漫谈:C语言 奇葩的指针定义规则

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 C语言的语法很麻拐。 初学者的…...

spring boot中一般如何使用线程池

在Spring Boot中&#xff0c;线程池作为并发编程的核心工具&#xff0c;对于提升应用程序性能、优化资源利用和保证系统稳定性具有重要作用。本文将详细阐述如何在Spring Boot中正确使用线程池&#xff0c;包括配置参数、实例化、任务提交、监控及常见问题处理等环节&#xff0…...

Shader 纹理动画和顶点动画

一、内置变量--时间 要实现动画&#xff0c;我们需要把时间添加到计算当中&#xff0c;让画面可以随着时间变化而变化。在Unity Shader提供了如下关于时间的内置变量以便于在shader中访问时间实现各种动态效果。 名称类型描述_Timefloat4t是自该场景加载开始所经过的时间&…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...