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

代码随想录算法训练营第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背包问题二维 二维数组&#xff0c;一维为物品&#xff0c;二维为背包重量 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中的报错场景

中国联通软件研究院&#xff08;简称联通软研院&#xff09;在全面评估与广泛调研后&#xff0c;在 2021年底决定采用OceanBase 作为基础&#xff0c;自研分布式数据库产品CUDB&#xff08;即China Unicom Database&#xff0c;中国联通数据库&#xff09;。目前&#xff0c;该…...

IDEA 接入 Deepseek

在本篇文章中&#xff0c;我们将详细介绍如何在 JetBrains IDEA 中使用 Continue 插件接入 DeepSeek&#xff0c;让你的 AI 编程助手更智能&#xff0c;提高开发效率。 一、前置准备 在开始之前&#xff0c;请确保你已经具备以下条件&#xff1a; 安装了 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)

你是否曾经因为害怕失败而逃避选择&#xff1f;是否因为不敢拒绝别人而让自己陷入困境&#xff1f;是否因为过于友善而被人轻视&#xff1f;如果你也曾为这些问题困扰&#xff0c;那么今天的博客就是为你准备的。我们将从行动、拒绝、自我认知、实力提升等多个角度&#xff0c;…...

C# OnnxRuntime部署DAMO-YOLO人头检测

目录 说明 效果 模型信息 项目 代码 下载 参考 说明 效果 模型信息 Model Properties ------------------------- --------------------------------------------------------------- Inputs ------------------------- name&#xff1a;input tensor&#xff1a;Floa…...

基于GeoTools的GIS专题图自适应边界及高宽等比例生成实践

目录 前言 一、原来的生成方案问题 1、无法自动读取数据的Bounds 2、专题图高宽比例不协调 二、专题图生成优化 1、直接读取矢量数据的Bounds 2、专题图成果抗锯齿 3、专题成果高宽比例自动调节 三、总结 前言 在当今数字化浪潮中&#xff0c;地理信息系统&#xff08;…...

各种DCC软件使用Datasmith导入UE教程

3Dmax: 先安装插件 https://www.unrealengine.com/zh-CN/datasmith/plugins 左上角导出即可 虚幻中勾选3个插件,重启引擎 左上角选择文件导入即可 Blender导入Datasmith进UE 需要两个插件, 文章最下方链接进去下载安装即可 一样的,直接导出,然后UE导入即可 C4D 直接保存成…...

尚硅谷爬虫note15

一、当当网 1. 保存数据 数据交给pipelines保存 items中的类名&#xff1a; DemoNddwItem class DemoNddwItem(scrapy.Item): 变量名 类名&#xff08;&#xff09; book DemoNddwItem(src src, name name, price price)导入&#xff1a; from 项目名.items import 类…...

云原生系列之本地k8s环境搭建

前置条件 Windows 11 家庭中文版&#xff0c;版本号 23H2 云原生环境搭建 操作系统启用wsl(windows subsystem for linux) 开启wsl功能&#xff0c;如下图 安装并开启github加速器 FastGithub 2.1 下载地址&#xff1a;点击下载 2.2 解压安装文件fastgithub_win-x64.zip 2…...

关于tomcat使用中浏览器打开index.jsp后中文显示不正常是乱码,但英文正常的问题

如果是jsp文件就在首行加 “<% page language"java" contentType"text/html; charsetUTF-8" pageEncoding"UTF-8" %>” 如果是html文件 在head标签加入&#xff1a; <meta charset"UTF-8"> 以jsp为例子&#xff0c;我们…...

mysql foreign_key_checks

‌foreign_key_checks‌是一个用于设置是否在DML/DDL操作中检查外键约束的系统变量。该变量默认启用&#xff0c;通常在正常操作期间启用以强制执行参照完整性。 功能描述 foreign_key_checks用于控制是否在DML&#xff08;数据操纵语言&#xff09;和DDL&#xff08;数据定义…...

开发环境搭建-06.后端环境搭建-前后端联调-Nginx反向代理和负载均衡概念

一.前后端联调 我们首先来思考一个问题 前端的请求地址是&#xff1a;http://localhost/api/employee/login 后端的接口地址是&#xff1a;http://localhost:8080/admin/employee/login 明明请求地址和接口地址不同&#xff0c;那么前端是如何请求到后端接口所响应回来的数…...

REST API前端请求和后端接收

1、get请求&#xff0c;带"?" http://localhost:8080/api/aop/getResult?param123 GetMapping("getResult")public ResponseEntity<String> getResult(RequestParam("param") String param){return new ResponseEntity<>("12…...

道可云人工智能每日资讯|《奇遇三星堆》VR沉浸探索展(淮安站)开展

道可云元宇宙每日简报&#xff08;2025年3月5日&#xff09;讯&#xff0c;今日元宇宙新鲜事有&#xff1a; 《奇遇三星堆》VR沉浸探索展&#xff08;淮安站&#xff09;开展 近日&#xff0c;《奇遇三星堆》VR沉浸探索展&#xff08;淮安站&#xff09;开展。该展将三星堆文…...

服务器数据恢复—raid5阵列中硬盘掉线导致上层应用不可用的数据恢复案例

服务器数据恢复环境&故障&#xff1a; 某公司一台服务器&#xff0c;服务器上有一组由8块硬盘组建的raid5磁盘阵列。 磁盘阵列中2块硬盘的指示灯显示异常&#xff0c;其他硬盘指示灯显示正常。上层应用不可用。 服务器数据恢复过程&#xff1a; 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聊天机器人(二)

继续上文&#xff0c;硬件软件准备齐全&#xff0c;介绍一下主要用到的库 sherpa-onnx 开源的&#xff0c;语音转文本、文本转语音、说话人分类和 VAD&#xff0c;关键是支持C#开发 OllamaSharp 用于连接ollama&#xff0c;如其名C#开发 虽然离可玩还有一段距离&#xff0…...

pyside6学习专栏(九):在PySide6中使用PySide6.QtCharts绘制6种不同的图表的示例代码

PySide6的QtCharts类支持绘制各种型状的图表&#xff0c;如面积区域图、饼状图、折线图、直方图、线条曲线图、离散点图等&#xff0c;下面的代码是采用示例数据绘制这6种图表的示例代码,并可实现动画显示效果&#xff0c;实际使用时参照代码中示例数据的格式将实际数据替换即可…...

DVI分配器2进4出,2进8出,2进16出,120HZ

DVI&#xff08;Digital Visual Interface&#xff09;分配器GEFFEN/HDD系列是一种设备&#xff0c;它能够将一个DVI信号源的内容复制到多个显示设备上。根据您提供的信息&#xff0c;这里我们关注的是具有2个输入端口和多个&#xff08;4个、8个或16个&#xff09;输出端口的D…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...