代码随想录算法训练营第35天 | 01背包问题二维、01背包问题一维、416. 分割等和子集
一、01背包问题二维
二维数组,一维为物品,二维为背包重量
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int bag = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i=0; i<n ; i++){weight[i] = scanner.nextInt();}for(int j=0; j<n ; j++){value[j] = scanner.nextInt();}int[][] dp = new int[n][bag+1];for(int j=weight[0]; j<=bag ; j++){dp[0][j] = value[0];}for(int i = 1 ; i<n ; i++){for(int j=0; j<=bag ; j++){if(j<weight[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);}}}System.out.println(dp[n - 1][bag]);}
}
二、01背包问题一维
在一维数组上更新,pd[j] 为容量为j的背包容纳的最大价值。
第一层循环是每个物品,第二层循环要从背包容量向前循环到当前物品重量,更新时判断【当前容量最大价值】和【放入当前物品后的总价值】的最高值。
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int bag = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i=0; i<n ; i++){weight[i] = scanner.nextInt();}for(int j=0; j<n ; j++){value[j] = scanner.nextInt();}int[] dp = new int [bag+1];for (int i = 0; i < n; i++) {for (int j = bag; j >= weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bag]);}
}
三、416. 分割等和子集
利用背包问题的思路,看能否装满sum/2的背包,物品的重量和价值一样都是元素的数值
class Solution {public boolean canPartition(int[] nums) {if(nums ==null || nums.length < 2) return false;int sum = 0;for(int num : nums){sum += num;}if(sum%2 == 1) return false;int target = sum/2;int[] dp = new int[target+1];for(int i = 0 ; i<nums.length; i++){for(int j = target ; j>=nums[i] ; j--){dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}if(dp[target]==target) return true;}return dp[target]==target;}
}
相关文章:
代码随想录算法训练营第35天 | 01背包问题二维、01背包问题一维、416. 分割等和子集
一、01背包问题二维 二维数组,一维为物品,二维为背包重量 import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner new Scanner(System.in);int n scanner.nextInt();int bag scanner.nextInt();int[…...
与中国联通技术共建:通过obdiag分析OceanBase DDL中的报错场景
中国联通软件研究院(简称联通软研院)在全面评估与广泛调研后,在 2021年底决定采用OceanBase 作为基础,自研分布式数据库产品CUDB(即China Unicom Database,中国联通数据库)。目前,该…...
IDEA 接入 Deepseek
在本篇文章中,我们将详细介绍如何在 JetBrains IDEA 中使用 Continue 插件接入 DeepSeek,让你的 AI 编程助手更智能,提高开发效率。 一、前置准备 在开始之前,请确保你已经具备以下条件: 安装了 JetBrains IDEA&…...
斗地主小游戏
<!DOCTYPE html> <html><head><meta charset="utf-8"><title>斗地主</title><style>.game-container {width: 1000px;height: 700px;margin: 0 auto;position: relative;background: #35654d;border-radius: 10px;padding…...
如何改变怂怂懦弱的气质(2)
你是否曾经因为害怕失败而逃避选择?是否因为不敢拒绝别人而让自己陷入困境?是否因为过于友善而被人轻视?如果你也曾为这些问题困扰,那么今天的博客就是为你准备的。我们将从行动、拒绝、自我认知、实力提升等多个角度,…...
C# OnnxRuntime部署DAMO-YOLO人头检测
目录 说明 效果 模型信息 项目 代码 下载 参考 说明 效果 模型信息 Model Properties ------------------------- --------------------------------------------------------------- Inputs ------------------------- name:input tensor:Floa…...
基于GeoTools的GIS专题图自适应边界及高宽等比例生成实践
目录 前言 一、原来的生成方案问题 1、无法自动读取数据的Bounds 2、专题图高宽比例不协调 二、专题图生成优化 1、直接读取矢量数据的Bounds 2、专题图成果抗锯齿 3、专题成果高宽比例自动调节 三、总结 前言 在当今数字化浪潮中,地理信息系统(…...
各种DCC软件使用Datasmith导入UE教程
3Dmax: 先安装插件 https://www.unrealengine.com/zh-CN/datasmith/plugins 左上角导出即可 虚幻中勾选3个插件,重启引擎 左上角选择文件导入即可 Blender导入Datasmith进UE 需要两个插件, 文章最下方链接进去下载安装即可 一样的,直接导出,然后UE导入即可 C4D 直接保存成…...
尚硅谷爬虫note15
一、当当网 1. 保存数据 数据交给pipelines保存 items中的类名: DemoNddwItem class DemoNddwItem(scrapy.Item): 变量名 类名() book DemoNddwItem(src src, name name, price price)导入: from 项目名.items import 类…...
云原生系列之本地k8s环境搭建
前置条件 Windows 11 家庭中文版,版本号 23H2 云原生环境搭建 操作系统启用wsl(windows subsystem for linux) 开启wsl功能,如下图 安装并开启github加速器 FastGithub 2.1 下载地址:点击下载 2.2 解压安装文件fastgithub_win-x64.zip 2…...
关于tomcat使用中浏览器打开index.jsp后中文显示不正常是乱码,但英文正常的问题
如果是jsp文件就在首行加 “<% page language"java" contentType"text/html; charsetUTF-8" pageEncoding"UTF-8" %>” 如果是html文件 在head标签加入: <meta charset"UTF-8"> 以jsp为例子,我们…...
mysql foreign_key_checks
foreign_key_checks是一个用于设置是否在DML/DDL操作中检查外键约束的系统变量。该变量默认启用,通常在正常操作期间启用以强制执行参照完整性。 功能描述 foreign_key_checks用于控制是否在DML(数据操纵语言)和DDL(数据定义…...
开发环境搭建-06.后端环境搭建-前后端联调-Nginx反向代理和负载均衡概念
一.前后端联调 我们首先来思考一个问题 前端的请求地址是:http://localhost/api/employee/login 后端的接口地址是:http://localhost:8080/admin/employee/login 明明请求地址和接口地址不同,那么前端是如何请求到后端接口所响应回来的数…...
REST API前端请求和后端接收
1、get请求,带"?" http://localhost:8080/api/aop/getResult?param123 GetMapping("getResult")public ResponseEntity<String> getResult(RequestParam("param") String param){return new ResponseEntity<>("12…...
道可云人工智能每日资讯|《奇遇三星堆》VR沉浸探索展(淮安站)开展
道可云元宇宙每日简报(2025年3月5日)讯,今日元宇宙新鲜事有: 《奇遇三星堆》VR沉浸探索展(淮安站)开展 近日,《奇遇三星堆》VR沉浸探索展(淮安站)开展。该展将三星堆文…...
服务器数据恢复—raid5阵列中硬盘掉线导致上层应用不可用的数据恢复案例
服务器数据恢复环境&故障: 某公司一台服务器,服务器上有一组由8块硬盘组建的raid5磁盘阵列。 磁盘阵列中2块硬盘的指示灯显示异常,其他硬盘指示灯显示正常。上层应用不可用。 服务器数据恢复过程: 1、将服务器中所有硬盘编号…...
【Pandas】pandas Series swaplevel
Pandas2.2 Series Computations descriptive stats 方法描述Series.argsort([axis, kind, order, stable])用于返回 Series 中元素排序后的索引位置的方法Series.argmin([axis, skipna])用于返回 Series 中最小值索引位置的方法Series.argmax([axis, skipna])用于返回 Series…...
esp32s3聊天机器人(二)
继续上文,硬件软件准备齐全,介绍一下主要用到的库 sherpa-onnx 开源的,语音转文本、文本转语音、说话人分类和 VAD,关键是支持C#开发 OllamaSharp 用于连接ollama,如其名C#开发 虽然离可玩还有一段距离࿰…...
pyside6学习专栏(九):在PySide6中使用PySide6.QtCharts绘制6种不同的图表的示例代码
PySide6的QtCharts类支持绘制各种型状的图表,如面积区域图、饼状图、折线图、直方图、线条曲线图、离散点图等,下面的代码是采用示例数据绘制这6种图表的示例代码,并可实现动画显示效果,实际使用时参照代码中示例数据的格式将实际数据替换即可…...
DVI分配器2进4出,2进8出,2进16出,120HZ
DVI(Digital Visual Interface)分配器GEFFEN/HDD系列是一种设备,它能够将一个DVI信号源的内容复制到多个显示设备上。根据您提供的信息,这里我们关注的是具有2个输入端口和多个(4个、8个或16个)输出端口的D…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
