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

背包问题（java)实现

news 来源：原创 2025/9/17 20:30:19

1、01背包

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] dp=new int[n+1][m+1];int[] v=new int[n+1];int[] w=new int[n+1];for(int i=1;i<=n;i++) {v[i]=scan.nextInt();w[i]=scan.nextInt();}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(v[i]>j) {dp[i][j]=dp[i-1][j];}else {dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i] );}}}System.out.println(dp[n][m]);}    
}

2、完全背包


import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] dp=new int[n+1][m+1];int[] v=new int[n+1];int[] w=new int[n+1];for(int i=1;i<=n;i++) {v[i]=scan.nextInt();w[i]=scan.nextInt();}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {dp[i][j]=dp[i-1][j];if(j>=v[i]) {dp[i][j]=Math.max(dp[i][j], dp[i][j-v[i]]+w[i]);}}}    System.out.println(dp[n][m]);}
}

3、多重背包1

数据范围

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][] dp=new int[n+1][m+1];int[] v=new int[n+1]; //体积int[] w=new int[n+1]; //价值int[] c=new int[n+1]; //重量for(int i=1;i<=n;i++) {v[i]=scan.nextInt();w[i]=scan.nextInt();c[i]=scan.nextInt();}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {dp[i][j]=dp[i-1][j];for(int k=1;k<=c[i]&&v[i]*k<=j;k++) {dp[i][j]=Math.max(dp[i][j], dp[i-1][j-v[i]*k]+w[i]*k);}System.out.print(dp[i][j]+" ");}System.out.println();}    System.out.println(dp[n][m]);}
}

4、多重背包2

数据范围

import java.util.Scanner;
import java.util.ArrayList;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt();// 使用列表存储二进制优化后的物品int[] newV = new int[2000*11];int[] newW = new int[2000*11];int[] dp = new int[m + 1];int count = 0;// 二进制优化处理for (int i = 1; i <= n; i++) {int v = in.nextInt();int w = in.nextInt();int c = in.nextInt();// 二进制拆分（将数量c分解为1,2,4...的幂次方组合）for (int k = 1; k <= c; k *= 2) {newV[count]=(v * k);newW[count]=(w * k);c -= k;count++;}if (c > 0) {newV[count]=(v * c);newW[count]=(w * c);count++;}}// 转化为01背包问题for (int i = 0; i < count; i++) {// 01背包处理逻辑for (int j = m; j >= newV[i]; j--) {dp[j] = Math.max(dp[j], dp[j - newV[i]] + newW[i]);}}System.out.println(dp[m]);}
}

背包问题（java)实现

1、01背包 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][] dpnew int[n1][m1];int[] vnew int[n1];int[] wnew int[n1];for(int i1;i<n;i) {v…...

编程日记 2025/9/17 20:30:19

HDCP（一）

HDCP的核心目标解析 1. 数字内容版权保护 HDCP（高带宽数字内容保护）的核心目标是防止未经授权的设备对高清音视频内容进行非法复制或截取。它通过加密技术保护数字信号在传输链路（如HDMI、DisplayPort、DVI等接口）中的安全性&am…...

编程日记 2025/9/17 13:23:34

HTTP 1.0 时代，第一次优化

HTTP 是 “HyperText Transfer Protocol” 的缩写，即超文本传输协议。相较于最初的设计，1.0增加了以下特性： 增加head，post等新方法。引入新方法是为了扩充语义，其中 head 方法可以只拿元信息，不必传输…...

编程日记 2025/9/17 20:28:30

【吾爱出品】[Windows] 鼠标或键盘可自定义可同时多按键连点工具

[Windows] 鼠标或键盘连点工具链接：https://pan.xunlei.com/s/VONSFKLNpyVDeYEmOCBY3WZJA1?pwduik5# [Windows] 鼠标或键盘可自定义可同时多按键连点工具就是个连点工具，功能如图所示，本人系统win11其他系统未做测试，自己玩…...

编程日记 2025/9/17 20:28:30

计算机网络起源

互联网的起源和发展是一个充满创新、突破和变革的历程，从20世纪60年代到1989年，这段时期为互联网的诞生和普及奠定了坚实的基础。让我们详细回顾这一段激动人心的历史。计算机的发展与ARPANET的建立（20世纪60年代） 互联网的诞生…...

编程日记 2025/9/17 20:27:11

Vue3 watch 与 watchEffect 深度解析

Vue3 watch 与 watchEffect 深度解析一、响应式监听的基石作用在Vue3的响应式系统中，watch和watchEffect是构建复杂状态逻辑的关键工具。它们实现了对响应式数据的精准监听，支撑着现代前端开发中的状态管理、副作用处理等核心功能。 1.1 演变 Optio…...

编程日记 2025/9/17 20:27:12

服务器信息收集

信息收集又叫打点，打仗也要侦探敌情，攻防更是如此。但要获取哪些信息呢？ 目录一. 获取公网IP 如何知道一个网站用了CDN？ 如何绕过CDN？ 二. 旁站信息收集三. C段主机查询四. 子域名信息收集五. 端口信息收…...

编程日记 2025/9/17 20:25:38

Java设计模式之装饰器模式：从入门到架构级实践

一、开篇：为什么需要装饰器模式？ 在软件开发中，我们经常面临这样的困境：如何在不修改原有对象结构的情况下，动态地扩展对象的功能？当系统需要为对象添加多种可能的扩展功能时，如果直接使用继承…...

编程日记 2025/9/13 15:37:13

Vue3性能优化全攻略：从原理到极致性能实战

一、性能瓶颈深度诊断 1.1 关键性能指标分析 1.2 性能剖析工具矩阵工具类型典型工具适用场景检测维度综合检测工具Lighthouse首屏加载性能分析加载评分/优化建议运行时监控工具Web Vitals页面交互性能监控FCP/LCP/TTI等框架专项工具Vue Devtools组件渲染性能分析渲染耗时/更…...

编程日记 2025/9/16 1:31:50

阿里云 AI 搜索开放平台：从算法到业务——AI 搜索驱动企业智能化升级

——已获知乎作者【GitHub Daily】授权转载目前大模型的强大能力，使其成为一些企业和行业的主要创新驱动力，企业亟需重新审视和调整现有的创新机制，以适应AI技术和大数据的快速发展。目前很多企业已经开始尝试大模型在业务中进行赋能&#x…...

编程日记 2025/8/29 6:40:01

特权FPGA之AT24C02 IIC实现

0 简介 IIC的物理层 IIC一共有只有两个总线： 一条是双向的串行数据线ＳＤＡ，一条是串行时钟线ＳＣＬ. SDA(Serial data)是数据线，D代表Data也就是数据，Send Data …...

编程日记 2025/9/9 6:04:44

Docker 容器内运行程序的性能开销

在 Docker 容器内运行程序通常会有一定的性能开销，但具体损失多少取决于多个因素。以下是详细分析： 1. CPU 性能理论开销：容器直接共享宿主机的内核，CPU 调度由宿主机管理，因此 CPU 运算性能几乎与原生环境一致&…...

编程日记 2025/9/9 21:07:48

SpringBoot依赖冲突引发的 log4j 日志打印问题及解决方法

依赖冲突引发的 log4j 日志打印问题及解决方法在软件开发过程中，依赖管理是至关重要的一环。然而，时常会遇到依赖冲突的情况，其中就包括影响日志框架正常使用，比如因依赖冲突导致无法正常打印 log4j 日志的问题。问题描述当…...

编程日记 2025/9/11 1:24:00

MacOS中的鼠标、触控板的设置研究

一、背景和写这篇文章的原因想搞清楚和配置好鼠标，比如解决好为什么我的滚动那么难用？怎么设置滚轮的方向跟windows相同？调整双击速度，调整鼠标滚轮左右拨动的"冷却时间"。二、各种设置之详细解释 1. MacOS设置 -&…...

编程日记 2025/9/4 5:22:48

Clickhouse试用单机版部署

问题最近需要试用clklog数据收集的社区版，clklog用数据库是Clickhouse。这就需要我先单机部署一个Clickhouse数据库，先试用试用。步骤这里假设我们已经拥有一台Ubuntu的服务器了，现在我们需要在这台机器上面安装Clickhouse数据库。Clic…...

编程日记 2025/9/14 9:23:08

【运维 | 硬件】服务器中常见的存储插槽类型、对应的传输协议及其特性总结

Why：最近更换设备，具体了解一下。传输协议对比协议底层接口最大带宽队列深度典型延迟适用场景 AHCI SATA 6 Gbps (~600 MB/s) 单队列（32命令） 较高传统 HDD/SATA SSD SAS SAS 24 Gbps (~2.4 GB/s) 单队列&…...

编程日记 2025/9/9 0:27:21

本地laravel项目【dcat-admin】部署到liunx服务器

文章目录前言一、部署流程1、数据库搬迁2、宝塔创建网站，配置php3、修改nginx配置4、在public目录设置软连接5、修改env配置、刷新缓存二、其他问题1.后台登陆失败问题2.完美解决接口跨域问题总结前言 laravel新手记录差不多一个月，总算用laravel…...

编程日记 2025/9/17 15:08:18

DeepSeek：AI如何重构搜索引擎时代的原创内容生态

一、当生成式AI遇上搜索引擎：一场效率与价值的博弈 2023年，全球搜索引擎处理了超过2万亿次查询，其中超40%涉及复杂问题解答。而与此同时，Google的"Helpful Content Update"算法升级直接淘汰了26%的低质AI生成页面。这场…...

编程日记 2025/9/12 18:44:40

在docker里装rocketmq-console

首先要到github下载（这个一般是需要你有梯子） GitHub - apache/rocketmq-externals at release-rocketmq-console-1.0.0 如果没有梯子，用下面这个百度网盘链接下 http://链接: https://pan.baidu.com/s/1x8WQVmaOBjTjss-3g01UPQ 提取码: fu…...

编程日记 2025/9/12 21:23:54

蓝桥杯C++组算法知识点整理 · 考前突击（上）【小白适用】

【背景说明】本文的作者是一名算法竞赛小白，在第一次参加蓝桥杯之前希望整理一下自己会了哪些算法，于是有了本文的诞生。分享在这里也希望与众多学子共勉。如果时间允许的话，这一系列会分为上中下三部分和大家见面，祝大家竞赛顺利…...

编程日记 2025/8/17 23:36:30

Docker 是什么？ Docker 基本观念介绍与容器和虚拟机的比较

🧑 博主简介：CSDN博客专家，历代文学网（PC端可以访问：历代文学，移动端可微信小程序搜索“历代文学”）总架构师，15年工作经验，精通Java编程，高并发设计&#xf…...

编程日记 2025/9/16 0:41:52

Docker：安装与部署 Nacos 的技术指南

1、简述 Nacos（Dynamic Naming and Configuration Service）是阿里巴巴开源的一个动态服务发现、配置管理和服务治理的综合解决方案，适用于微服务架构。 Nacos 主要功能：服务发现与注册：支持 Dubbo、Spring Cloud 等主流微服务框架的服务发现与注册。动态配置管理：支持…...

编程日记 2025/9/11 17:18:57

UE5 RPC调用示例详解

文章目录前言一、示例场景二、代码实现三、关键点解析3.1 RPC类型选择3.2 可靠性设置3.3 权限控制3.4 输入处理四、测试与验证总结前言在UE5中，RPC（远程过程调用）是实现多人游戏逻辑同步的核心机制。以下通过一个玩家跳跃的示例&#xf…...

编程日记 2025/9/9 10:19:40

MATLAB在工程领域的实际应用案例

文章目录前言自动驾驶汽车路径规划系统汽车先进驾驶辅助系统（ADAS）开发控制电气系统设计与优化桥梁结构分析与安全性评估前言 MATLAB 在工程领域应用广泛，能解决复杂问题、优化系统设计。下面从不同工程领域选取了具有代表性的案例&#x…...

编程日记 2025/9/12 17:27:38

【完美解决】VSCode连接HPC节点，已配置密钥却还是提示需要输入密码

目录问题描述软件版本原因分析错误逻辑链解决方案总结问题描述本人在使用 VSCode Remote-SSH 插件连接超算集群节点时，遇到以下问题：已正确配置 SSH 密钥，且 VSCode 能识别密钥文件（如图1），但在…...

编程日记 2025/9/14 16:50:45

智能物联网网关策略部署

实训背景某智慧工厂需部署物联网网关，实现以下工业级安全管控需求： 设备准入控制：仅允许注册MAC地址的传感器接入（白名单：AA:BB:CC:DD:EE:FF）。协议合规性：禁止非Modbus TCP（端口…...

编程日记 2025/9/9 1:32:52

玩转代理 IP ：实战爬虫案例

在现代互联网环境下，爬虫不仅是数据获取的利器，也成为应对网站反爬机制的技术博弈。而在这场博弈中，"代理 IP" 是核心武器之一。本文将以高匿名的代理ip为核心，结合 Python 实战、代理策略设计、高匿技巧与反封锁优化&a…...

编程日记 2025/9/8 21:06:22

Deepseek解锁科研绘图新方式

在科研领域，一张清晰、准确且美观的图片往往能比冗长的文字更有效地传达研究成果。从展示实验数据的图表，到阐述理论模型的示意图，科研绘图贯穿于研究的各个环节。然而，传统的科研绘图工具往往操作复杂，学习成本高&…...

编程日记 2025/9/16 4:12:00

【unity游戏开发入门到精通——动画篇】Animator反向动力学（IK）

考虑到每个人基础可能不一样，且并不是所有人都有同时做2D、3D开发的需求，所以我把【零基础入门unity游戏开发】分为成了C#篇、unity通用篇、unity3D篇、unity2D篇。【C#篇】：主要讲解C#的基础语法，包括变量、数据类型、运算符、…...

编程日记 2025/9/9 1:32:54

【JavaScript】十八、页面加载事件和页面滚动事件

文章目录 1、页面加载事件1.1 load1.2 DOMContentLoaded 2、页面滚动事件2.1 语法2.2 获取滚动位置 3、案例：页面滚动显示隐藏侧边栏 1、页面加载事件 script标签在html中的位置一般在</body>标签上方，这是因为代码从上往下执行，在htm…...

编程日记 2025/9/4 11:05:29

Solana链开发全景指南：从环境搭建到生态实践

——2025年高性能区块链开发技术栈深度解析一、Solana核心优势与技术特性 1. 突破性技术架构历史证明（PoH）：通过时间戳序列化交易，实现并行处理能力，支持5万TPS的吞吐量并行执行引擎（Sealevel&#xf…...

编程日记 2025/9/16 3:45:38

这是一个文章标题

# Markdown 全语法示例手册本文档将全面演示 Markdown 的语法元素，包含 **标题**、**列表**、**代码块**、**表格**、**数学公式** 等 18 种核心功能。所有示例均附带实际应用场景说明。---## 一、基础文本格式### 1.1 标题层级 markdown # H1 (使用 #) ## H2 (使用…...

编程日记 2025/9/10 3:38:39

预言机与数据聚合器：DeFi的数据桥梁与风险博弈

一、核心机制与价值定位预言机（Oracle）与数据聚合器是DeFi生态的“数据基建层”，解决链上-链下数据互通与链上数据可读性两大问题： 数据输入层（预言机）：将现实世界数据（价格、天气…...

编程日记 2025/9/11 0:06:36

通过百度OCR在线API识别带水印扫描图片文字

目录 0 环境准备 1 百度OCR API申请 1.1 登录百度智能云 1.2 创建应用 1.3 获取API key和secret key 2 创建项目python环境 2.1 conda创建python环境 2.2 在pycharm中创建项目 2.3 激活python环境 2.4 安装项目依赖包 3 程序逻辑实现 3.1 导入依赖包 3.2 定义百度k…...

编程日记 2025/9/14 10:17:38

ocr python库

ocr python库上手Git、Gitee和Github！watt toolkit...

编程日记 2025/9/10 3:19:03

Node 处理 request 的过程中，都会更新哪些 metadata 和 property

什么是 Metadata？ 用于描述帧状态、控制参数、处理结果等是随 request 流动的结构，通常是 PerFrameMetaData，每一帧一份属于 HAL3 metadata 树的组成部分什么是 Property？ 是 CamX 内部定义的一种帧级别的轻量信息块不一…...

编程日记 2025/9/6 15:52:14

基于labview的多功能数据采集系统

基于labview的多功能数据采集系统（可定制功能） 包含基于NI温度采集卡。电流采集卡。电压采集卡的数据采集功能数据存储报表存储数据处理与分析生产者消费者架构有需要可联系...

编程日记 2025/9/8 13:10:59

李沐《动手学深度学习》 | 线性神经网络-线性回归

文章目录线性回归1.确定模型2.衡量预估质量-损失函数3.深度学习的基础优化算法随机梯度下降小批量随机梯度下降从线性回归到深度网络线性回归从0开始实现构造一个人造数据集创建数据集可视化数据集读取数据-随机抽取样本模型定义模型参数初始化定义模型定义损失函数定义优化…...

编程日记 2025/9/11 11:05:03

LabVIEW 中 “Flatten To Json String” VI 应用及优势

在 LabVIEW 开发涉及机器人数据等场景时，常需将数据以特定 JSON 格式输出。“Flatten To Json String” VI 在此过程中能发挥重要作用，相比 LabVIEW 系统自带的 JSON 处理方式，它具备独特优势。以下将介绍其获取、使用方法及相较系统自带方式…...

编程日记 2025/9/16 0:41:55

关于 Spring Boot 后端项目使用 Maven 打包命令、JAR/WAR 对比、内嵌服务器与第三方服务器对比，以及热部署配置的详细说明

以下是关于 Spring Boot 后端项目使用 Maven 打包命令、JAR/WAR 对比、内嵌服务器与第三方服务器对比，以及热部署配置的详细说明： 一、Maven 打包命令详解 1. 基础命令 1.1 清理并打包 mvn clean packageclean：删除 target 目录中的旧构建文…...

编程日记 2025/8/28 4:41:59

用labview写crc8校验

crc8校验有好几种，我这里写的是不带任何后缀的crc8。首先，我们百度一下crc8的计算方式一般搜索出来下面还有c语言写的crc8可以做为参考。下面便是根据百度的计算方式写的crc8，已校验过，无问题。写完后，可以输入下…...

编程日记 2025/9/6 9:50:01

阿里云CDN与DCDN主动推送静态资源至边缘服务器的ASP.NET WEB实例

一、CDN，需要调用PushObjectCache接口进行URL预热，以下是操作步骤： 1. 准备工作首先，安装阿里云SDK NuGet包： Install-Package Aliyun.NET.SDK.CDN -Version 3.0.0 Install-Package Aliyun.NET.SDK.Core -Version 3.0.0 2. 创建ASP.NET Web页面代码 CDNPreheat.aspx…...

编程日记 2025/9/9 13:33:04

LangChain-提示模板 (Prompt Templates)

提示模板是LangChain的核心组件，用于构建发送给语言模型的输入。本文档详细介绍了提示模板的类型、功能和最佳实践。概述提示工程是使用大型语言模型的关键技术。通过精心设计的提示，可以显著提高模型的输出质量和相关性。LangChain的提示模板系统提…...

编程日记 2025/9/11 19:40:44

多线程中的互斥与同步

多线程中的互斥与同步 1. 互斥与同步的区别互斥：确保某一资源在同一时刻只能被一个线程访问。其主要目的是保证资源的唯一性和排他性，但无法控制访问的顺序。同步：在互斥的基础上，进一步通过其他机制保证访问资源的有序性。 2…...

编程日记 2025/9/17 10:45:15

ValueError: Cannot handle batch sizes ＞ 1 if no padding token is defined`

ValueError: Cannot handle batch sizes > 1 if no padding token is defined` batch sizes > 1 进行掩码填充：pad_token，eos_token 在处理自然语言处理任务时，尤其是在使用批量数据进行训练或推理时，经常需要对输入文本进行填充（padding），以确保每个输入序列具…...

编程日记 2025/9/8 4:46:31

Gemma 3模型：Google 开源新星，大语言模型未来探索

🐇明明跟你说过：个人主页 🏅个人专栏：《深度探秘：AI界的007》 🏅 🔖行路有良友，便是天堂🔖 目录一、引言 1、快速发展的AI世界：为何关注Gemma 3&#x…...

编程日记 2025/9/7 1:26:27

先占个日常，等会写。

引入一个重要的概念 “struct” （译为中文：结构体） 可用作设出比较复杂的一些变量类型语法 ：struct point name { int x; int y; int z;} point 和 name是任意命名的名字，含义是，声明一个变量类型为st…...

编程日记 2025/9/6 7:49:28

PyTorch Tensor维度变换实战：view/squeeze/expand/repeat全解析

本文从图像数据处理、模型输入适配等实际场景出发，系统讲解PyTorch中view、squeeze、expand和repeat四大维度变换方法。通过代码演示对比不同方法的适用性，助您掌握数据维度调整的核心技巧。一、基础维度操作方法 1. view：内存连续的形状重…...

编程日记 2025/9/10 20:41:35

212、【图论】字符串接龙（Python）

题目描述题目链接：110. 字符串接龙代码实现 import collectionsn int(input()) beginStr, endStr input().split() strList [input() for _ in range(n)]deque collections.deque() # 使用队列遍历结点 deque.append([beginStr, 1]) # 存储当前字符串和遍…...

编程日记 2025/9/7 8:01:18

土堆教程笔记【PyTorch】

官网：torch — PyTorch 2.6 documentation Pycharm 解释器一般搞深度学习都用虚拟环境的解释器，为了满足不同的项目所需要的不同的包的版本。 1. system interpreter表示本地的解释器也就是你电脑系统里安装的解释器 2. Virtual Environment—Py…...

编程日记 2025/9/13 16:54:25

1、01背包

2、完全背包

3、多重背包1

4、多重背包2

相关文章：