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

Day42 动态规划 part04

Day42 动态规划 part04

46. 携带研究材料(卡哥的卡码网的题目)

背包问题

我的思路:
写不了一点儿…T^T
总结规律就是,dp数组要比原来各个size + 1,dp[i][j] = Math.max(xxx, xxxx(根据题目情况进行各种处理))

解答:

import java.util.*;public class Main {public static void main (String[] args) {Scanner myScanner = new Scanner(System.in);int goodSize = myScanner.nextInt();int bagSize = myScanner.nextInt();int[] weight = new int[goodSize];int[] value = new int[goodSize];for(int i = 0; i < goodSize; i++) {weight[i] = myScanner.nextInt();}for(int i = 0; i < goodSize; i++) {value[i] = myScanner.nextInt();}BagProblem(weight, value, bagSize);}public static void BagProblem(int[] weight, int[] value, int bagSize) {int[][] dp = new int[weight.length + 1][bagSize + 1];for(int i = 1; i < dp.length; i++) {for(int j = 1; j < dp[0].length; j++) {if(j < weight[i - 1]) {dp[i][j] = dp[i - 1][j];}else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);}}}System.out.println(dp[dp.length - 1][bagSize]);}
}

416. 分割等和子集

我的思路:
笑死,已经学会抢答了!!
不管怎么样,模板是一把子背住了

		int[] dp = new int[xxx+ 1];for(int i = 0; i < dp.length; i++) {for(int j = xxx; j < xxx; j++) {dp[j] = Math.max(xxx, xxx);}}

题解思路应该是,数组之和的一半sum(nums)/2,dp数组是长度为 sum(nums)/2 + 1(总结规律,size + 1),从后向前(不一样了)不断比较并且更新最大值,如果dp数组最后一个值 == sum(nums)/2,那么就说明可以划分成两个和相等的子集

解答:

class Solution {public boolean canPartition(int[] nums) {int sum = Arrays.stream(nums).sum();if(sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < nums.length; i++) {for(int j = dp.length - 1; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}if(target == dp[target]) {return true;}}return target == dp[target];}
}

相关文章:

Day42 动态规划 part04

Day42 动态规划 part04 46. 携带研究材料(卡哥的卡码网的题目) 背包问题 我的思路: 写不了一点儿…T^T 总结规律就是&#xff0c;dp数组要比原来各个size 1&#xff0c;dp[i][j] Math.max(xxx, xxxx&#xff08;根据题目情况进行各种处理&#xff09;) 解答&#xff1a; …...

python set是什么类型

python set是一种数据类型&#xff0c;数学里的集合概念&#xff0c;在Python语言里对应的是set类型。与list&#xff0c;tuple不同的地方是&#xff0c;set更加强调的是一种“从属关系”&#xff08;membership&#xff09;&#xff0c;跟顺序无关&#xff0c;所以有重复的元素…...

redis事务(redis features)

redis支持事务&#xff0c;也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务&#xff0c;事务开启之后&#xff0c;所有的命令就都会被放入到一个队列中&#xff0c;最后通过一个EXEC命令来执行事务中…...

SpringBoot整合minio

SpringBoot整合minio 1. 下载及安装1.1 windows版本1.2 Linux版本 2. SpringBoot整合minio2.1 依赖2.2 配置文件2.3 配置类2.4 工具类2.5 测试1. 业务层2. 控制层 1. 下载及安装 1.1 windows版本 目录结构 启动文件 标红的地方按实际安装地更改 echo off REM 声明采用UT…...

3090. 每个字符最多出现两次的最长子字符串

说在前面 &#x1f388;不知道大家对于算法的学习是一个怎样的心态呢&#xff1f;为了面试还是因为兴趣&#xff1f;不管是出于什么原因&#xff0c;算法学习需要持续保持。 题目描述 给你一个字符串 s &#xff0c;请找出满足每个字符最多出现两次的最长子字符串&#xff0c;…...

26.活锁、饥饿锁

两个线程&#xff0c;相互改变了对方结束条件&#xff0c;导致两个线程不能结束。执行时间也都是一样&#xff0c;导致两个线程永远不会结束。 Slf4j public class LiveLockDemo {static volatile int count 10;public static void main(String[] args) {new Thread(() ->…...

docker 安装nginx

一、先查看有没有nginx镜像 docker images 二、发现没有nginx镜像&#xff0c;下载最新镜像 docker pull nginx 三、运行镜像 为了先复制出部分文件&#xff0c;先启动一个临时容器 docker run --name nginx -p 9001:80 -d nginx docker cp nginx:/etc/nginx/conf.d /home/…...

2024年阿里云新用户便宜购买云服务器攻略:5大细节助你降低购买成本

随着互联网的蓬勃发展&#xff0c;无论是个人还是企业&#xff0c;拥有一个稳定且高效的网站或APP已成为提升竞争力的关键。为了将这些项目部署并运行起来&#xff0c;购买一台实用又便宜的云服务器是必不可少的。阿里云作为国内首屈一指的云服务提供商&#xff0c;自然成为了众…...

SSTI模板注入(jinja2)

前面学习了SSTI中的smarty类型&#xff0c;今天学习了Jinja2&#xff0c;两种类型都是flask框架的&#xff0c;但是在注入的语法上还是有不同 SSTI&#xff1a;服务器端模板注入&#xff0c;也属于一种注入类型。与sql注入类似&#xff0c;也是通过凭借进行命令的执行&#xff…...

ESP32学习---ESP-NOW(一)

ESP32学习---ESP-NOW&#xff08;一&#xff09; 官网简介arduino 官网简介 首先看官网的介绍&#xff1a;https://www.espressif.com.cn/zh-hans/solutions/low-power-solutions/esp-now ESP-NOW 是乐鑫定义的一种无线通信协议&#xff0c;能够在无路由器的情况下直接、快速…...

C++核心高级编程 --- 3、函数提高

文章目录 第三章&#xff1a;3.函数提高3.1 函数默认参数3.2 函数占位参数3.3 函数重载3.3.1 函数重载概述3.3.2 注意事项 第三章&#xff1a; 3.函数提高 3.1 函数默认参数 语法结构&#xff1a;返回值类型 函数名 (参数 默认值){} #include <iostream> using name…...

【微服务篇】深入理解分布式消息队列系统

分布式消息队列是一种在多个服务器、应用或服务之间进行消息传递的技术。它使得各个独立的组件可以通过异步消息进行通信&#xff0c;提高了系统的可扩展性、解耦性和可靠性。 典型应用场景 1. 异步处理 在许多系统中&#xff0c;某些任务的处理可能需要较长时间&#xff0c…...

基于k8s的web服务器构建

文章目录 k8s综合项目1、项目规划图2、项目描述3、项目环境4、前期准备4.1、环境准备4.2、ip划分4.3、静态配置ip地址4.4、修改主机名4.5、部署k8s集群4.5.1、关闭防火墙和selinux4.5.2、升级系统4.5.3、每台主机都配置hosts文件&#xff0c;相互之间通过主机名互相访问4.5.4、…...

【名词解释】ImageCaption任务中的CIDEr、n-gram、TF-IDF、BLEU、METEOR、ROUGE 分别是什么?它们是怎样计算的?

CIDEr CIDEr&#xff08;Consensus-based Image Description Evaluation&#xff09;是一种用于自动评估图像描述&#xff08;image captioning&#xff09;任务性能的指标。它主要通过计算生成的描述与一组参考描述之间的相似性来评估图像描述的质量。CIDEr的独特之处在于它考…...

C++其他语法..

1.运算符重载 之前有一个案例如下所示 其中我们可以通过add方法将两个点组成一个新的点 class Point {friend Point add(Point, Point);int m_x;int m_y; public:Point(int x, int y) : m_x(x), m_y(y) {}void display() {cout << "(" << m_x <<…...

【Vue3源码学习】— CH2.6 effect.ts:详解

effect.ts&#xff1a;详解 1. 理解activeEffect1.1 定义1.2 通过一个例子来说明这个过程a. 副作用函数的初始化b. 执行副作用函数前c. 访问state.countd. get拦截器中的track调用e. 修改state.count时的set拦截器f. trigger函数中的依赖重新执行 1.3 实战应用1.4 activeEffect…...

C语言:文件操作(一)

目录 前言 1、为什么使用文件 2、什么是文件 2.1 程序文件 2.2 数据文件 2.3 文件名 3、文件的打开和关闭 3.1 文件指针 3.2 文件的打开和关闭 结&#xff08;一&#xff09; 前言 本篇文章将介绍C语言的文件操作&#xff0c;在后面的内容讲到&#xff1a;为什么使用文…...

集中进行一系列处理——函数

需要多次执行相同的处理&#xff0c;除了编写循环语句之外&#xff0c;还可以集中起来对它进行定义。 对一系列处理进行定义的做法被称为函数&#xff0c;步骤&#xff0c;子程序。 对函数进行定一后&#xff0c;只需要调用该函数就可以了。如果需要对处理的内容进行修正&…...

git diff

1. 如何将库文件的变化生成到patch中 git diff --binary commit1 commit2 > test.patch 打patch&#xff1a; git apply test.patch 2. 如何消除trailing whitespace 问题 git diff --ignore-space-at-eol commit1 commit2 > test.patch 打patch&#xff1a; git ap…...

新手使用GIT上传本地项目到Github(个人笔记)

亲测下面的文章很有用处。 1. 初次使用git上传代码到github远程仓库 - 知乎 (zhihu.com) 2. 使用Git时出现refusing to merge unrelated histories的解决办法 - 知乎...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...