当前位置: 首页 > 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的解决办法 - 知乎...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...