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

01_背包问题

news 来源：原创 2025/9/6 15:12:14

package org.josh;

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 物品数量
long w = scanner.nextLong(); // 背包容量，使用long防止溢出
int[] v = new int[n]; // 存储每个物品的价值（这里视为重量）
for (int i = 0; i < n; i++) {
v[i] = scanner.nextInt();
}

    // 使用分治法将物品分成两组，分别计算子集和int mid = n / 2; // 将物品数组分为前半部分和后半部分List<Long> sumA = generateSubsetSums(v, 0, mid); // 前半部分的所有子集和List<Long> sumB = generateSubsetSums(v, mid, n); // 后半部分的所有子集和Collections.sort(sumB); // 对后半部分的子集和进行排序，便于后续二分查找long count = 0; // 统计有效子集组合的数量for (long a : sumA) { // 遍历前半部分的每个子集和aif (a > w) continue; // 剪枝：如果当前a已经超过背包容量，跳过long remaining = w - a; // 计算剩余可用容量// 在sumB中找到不大于remaining的元素个数，并累加到countint idx = upperBound(sumB, remaining);count += idx;}System.out.println(count); // 输出结果
}/*** 生成指定区间[start, end)内所有子集的和* @param v 物品数组* @param start 起始索引（包含）* @param end 结束索引（不包含）* @return 所有可能子集的和的列表*/
private static List<Long> generateSubsetSums(int[] v, int start, int end) {List<Long> sums = new ArrayList<>();int n = end - start; // 当前区间的元素个数// 遍历所有可能的子集（通过位掩码表示）for (int mask = 0; mask < (1 << n); mask++) {long sum = 0;// 检查每个位是否被选中，计算对应的子集和for (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) { // 第i位被选中sum += v[start + i]; // 将对应物品的价值累加}}sums.add(sum);}return sums;
}/*** 在已排序的列表中查找最后一个小于等于target的元素位置，返回符合条件元素的数量* @param list 已排序的列表* @param target 目标值* @return 列表中不大于target的元素个数*/
private static int upperBound(List<Long> list, long target) {int left = 0, right = list.size() - 1;int res = -1; // 初始化为-1，处理所有元素都大于target的情况while (left <= right) {int mid = (left + right) >>> 1; // 无符号右移防止溢出if (list.get(mid) <= target) {res = mid; // 记录当前位置，并继续向右查找可能的更大值left = mid + 1;} else {right = mid - 1; // 中间值过大，向左查找}}// res是最后一个符合条件的元素索引，返回数量为res+1（索引转个数）return res + 1;
}

}

相关文章：

01_背包问题

package org.josh; import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); // 物品数量 long w scanner.nextLong(); // 背包容量&#xff0c;使用long防止溢出 int[] v …...

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

ps 人像学习

视频&#xff1a; 一ps快捷键 1.1 创建图层 ctrlj 1.2 放大缩小图片的大小 按住alt 滚轮 1.3 移动图片 空格 左键 1.4 撤回 ctrlz 二 精修的第一步是去除斑点&#xff0c;瑕疵&#xff0c; 2.1 污点修复画笔工具 新建一个图层&#xff0c;点击污点修复工具进行修复…...

编程日记 2025/9/6 15:05:56

【AI论文】MM-IFEngine：迈向多模态指令遵循

摘要&#xff1a;指令遵循&#xff08;IF&#xff09;能力衡量多模态大语言模型&#xff08;MLLM&#xff09;准确理解用户告诉他们的内容以及他们是否做得正确的能力。 现有的多模态指令训练数据很少&#xff0c;基准测试简单&#xff0c;指令原子化&#xff0c;对于要求精确输…...

编程日记 2025/9/6 15:11:11

【C++初学】课后作业汇总复习（五） 单目运算符重载

本题主要考察-构造函数的定义和操作符重载、友元函数等 根据后缀和程序样例输出&#xff0c;完成分数类和相关函数的定义&#xff0c; 输入&#xff1a; -6 12 8 -16 输出&#xff1a; 1/2 1/1 -1/2 / -1/2 - -1/2 0/1 输入&#xff1a; 3 7 2 6 输出&#xff1a; 1/…...

编程日记 2025/9/5 23:52:55

Python基础语法速通（自用笔记）

目录 # 输出直接print就行了 # 次方&#xff0c;除法&#xff0c;取整 # 定义变量直接写就可以&#xff0c;不用写类型 # 基础的while不用写&#xff08;&#xff09;和{}&#xff0c;直接用冒号即可&#xff0c;缩进对齐 # 这里的for循环直接用in就可以,意思是从...中一个…...

编程日记 2025/9/5 20:01:45

Nginx基础讲解

Nginx基础讲解 Nginx 是一款高性能的 HTTP 服务器和反向代理服务器&#xff0c;广泛用于负载均衡、静态资源托管、SSL 终端等场景。以下是对 Nginx 的详细讲解&#xff1a; 1. Nginx 核心概念​ ​事件驱动架构​&#xff1a;基于异步非阻塞模型&#xff0c;高效处理高并发连接…...

编程日记 2025/9/6 7:32:33

K8S+Prometheus+Consul+alertWebhook实现全链路服务自动发现与监控、告警配置实战

系列文章目录 k8s服务注册到consul prometheus监控标签 文章目录 系列文章目录前言一、环境二、Prometheus部署1.下载2.部署3.验证 三、kube-prometheus添加自定义监控项1.准备yaml文件2.创建新的secret并应用到prometheus3.将yaml文件应用到集群4.重启prometheus-k8s pod5.访…...

编程日记 2025/9/5 22:54:45

组件安全工程化革命：从防御体系构建到安全基因重塑

文章目录 总起&#xff1a;数字世界的钢铁长城 分论&#xff1a; 一、组件生态的"七宗罪"与安全基因重组 二、百万级流量下的安全工程化实战 三、性能与安全的共生进化论 四、安全工程化全链路解决方案 总束&#xff1a;安全基因驱动的未来图景 五、时代思考…...

编程日记 2025/9/3 22:01:24

(PC+WAP)大气滚屏网站模板 电气电力设备网站源码下载

源码介绍 (PCWAP)大气滚屏网站模板 电气电力设备网站源码下载。PbootCMS内核开发的网站模板&#xff0c;该模板适用于滚屏网站模板、电气电力设备网站源码等企业&#xff0c;当然其他行业也可以做&#xff0c;只需要把文字图片换成其他行业的即可&#xff1b;PCWAP&#xff0c…...

编程日记 2025/8/29 3:14:18

发送加密信息的简单实现【Java】

&#xff08;修改期&#xff09; 一、代码的引用处 public static SecretKeys generateKeys() throws NoSuchAlgorithmException {: 定义一个公共静态方法&#xff0c;用于生成 AES 和 HMAC 密钥对。 public static String encrypt(String plaintext, SecretKey aesKey, S…...

编程日记 2025/9/1 23:47:52

阿里云域名解析

一、打开域名控制台 PC端浏览器打开阿里云域名控制台：域名控制台，点击"域名解析"。 二、添加解析设置 选择需要解析的域名，点击"解析设置"。 点击"添加记录"。 添加@和www即可。...

编程日记 2025/8/17 20:38:57

DNS域名解析服务（正向 反向 主从）

DNS 1.分散式管理&#xff1a; Hosts文件 一改百度就不会访问了 Ip地址 域名 121&#xff0e;226.246.3 www.jd.com 2.我们会搭建一台 域名解析服务器全世界得域名全靠这台服务器进行解析 中央集权制 域名是由多个部分组成的 www.baidu.com .baidu .com是域…...

编程日记 2025/8/31 14:56:32

ROS2---std_msgs基础消息包

std_msgs 是ROS 2&#xff08;Robot Operating System 2&#xff09;里的基础消息包&#xff0c;它定义了一系列简单却常用的消息类型&#xff0c;为不同节点间的通信提供了基础的数据格式。 1. 消息包概述 std_msgs 包包含了多种基础消息类型&#xff0c;这些类型用于表示常…...

编程日记 2025/9/5 3:55:20

python基础：数据类型转换、运算符(算术运算符、比较运算符、逻辑运算符、三元运算符、位运算符)

目录 一、类型转换 隐式类型转换/自动转换&#xff1a; 显示类型转换/强制转换&#xff1a; 二、运算符 算数运算符&#xff1a; - * / 比较运算符 逻辑/布尔运算符 赋值运算符&#xff1a; 三元运算符 位运算符 [二进制] 运算符优先级 一、类型转换 python变量的类…...

编程日记 2025/8/30 10:18:15

[特殊字符] 终端效率提升指南：zsh + tmux

在日常开发中&#xff0c;一个舒适、高效的终端环境能显著提升工作效率。本文将介绍如何通过配置 oh-my-zsh 和 tmux 打造一个功能强大、便捷实用的终端工具集。无论你是 Linux 新手&#xff0c;还是资深开发者&#xff0c;都能从中获得实用的提升技巧。 &#x1f300; 一、终…...

编程日记 2025/8/23 5:04:57

【Linux篇】深入理解文件系统：从基础概念到 ext2 文件系统的应用与解析

文件系统的魔法&#xff1a;让计算机理解并存储你的数据 一. 文件系统1.1 块1.2 分区1.3 inode(索引节点) 二. ext2文件系统2.1 认识文件系统2.2 Block Group (块组)2.2.1 Block Group 的基本概念2.2.2 Block Group 的作用 2.3 块组内部结构2.3.1 超级块&#xff08;Super Bloc…...

编程日记 2025/9/3 9:26:52

MarkDown 输出表格的方法

MarkDown用来输出表格很简单&#xff0c;比Word手搓表格简单多了&#xff0c;而且方便修改。 MarkDown代码&#xff1a; |A|B|C|D| |:-|-:|:-:|-| |1|b|c|d| |2|b|c|d| |3|b|c|d| |4|b|c|d| |5|b|c|d|显示效果&#xff1a; ABCD1bcd2bcd3bcd4bcd5bcd A列强制左对齐&#xf…...

编程日记 2025/9/6 0:27:43

DOM解析XML：Java程序员的“乐高积木式“数据搭建

各位代码建筑师们&#xff01;今天我们要玩一个把XML变成内存乐高城堡的游戏——DOM解析&#xff01;和SAX那种"边看监控边破案"的刺激不同&#xff0c;DOM就像把整个乐高说明书一次性倒进大脑&#xff0c;然后慢慢拼装&#xff08;内存&#xff1a;你不要过来啊&…...

编程日记 2025/8/30 13:26:15

Python 数组里找出子超集

碰见一个问题&#xff0c;有一个大数组&#xff0c;如下所示&#xff1a; xx [[1, 3, 4], [3, 4, 5], [1, 2, 3, 4, 5], [6], [7, 8], [6, 7, 8]]大数组里面有好多小的数组&#xff0c;观察发现&#xff0c;小的数组其实有挺多别的小数组的子集&#xff0c;现在问题来了&…...

编程日记 2025/8/31 20:26:25

上层 Makefile 控制下层 Makefile ---- 第二部分(补充一些例子与细节)

1. 递归调用子目录 Makefile 通过 $(MAKE) -C 进入子目录并执行其 Makefile&#xff0c;这是最常见的分层构建方法。 示例&#xff1a;基本递归调用 目录结构&#xff1a; project/ ├── Makefile # 顶层 Makefile ├── lib/ │ ├── Makefile # 子目录…...

编程日记 2025/9/5 14:08:09

LeetCode算法题(Go语言实现)_44

题目 有 n 个城市&#xff0c;其中一些彼此相连&#xff0c;另一些没有相连。如果城市 a 与城市 b 直接相连&#xff0c;且城市 b 与城市 c 直接相连&#xff0c;那么城市 a 与城市 c 间接相连。 省份是一组直接或间接相连的城市&#xff0c;组内不含其他没有相连的城市。 给你…...

编程日记 2025/9/5 3:37:35

STM32 HAL库之USART示例代码

串口发送和接收以及回调函数都可在这个文件中查询&#xff1a;stm32f1xx_hal_uart.h 串口配置初始化代码main.c中&#xff1a;MX_USART1_UART_Init();&#xff0c;初始化 UART 高层参数&#xff08;波特率、数据位、停止位、校验、模式等&#xff09; void MX_USART1_UART_In…...

编程日记 2025/9/3 22:49:47

头歌educoder——数据库 第10-11章

第10章 1、 事务的&#xff08; &#xff09;特性要求事务必须被视为一个不可分割的最小工作单元 A、 原子性 B、 一致性 C、 隔离性 D、 持久性 2、 事务的&#xff08; &#xff09;特性要求一个事务在执行时&#xff0c;不会受到其他事务的影响。 A、 原子性 B、 一致性 C…...

编程日记 2025/8/30 12:34:29

从 Vue 到 React：深入理解 useState 的异步更新与函数式写法

目录 从 Vue 到 React&#xff1a;深入理解 useState 的异步更新与函数式写法1. Vue 的响应式回顾&#xff1a;每次赋值立即生效2. React 的状态更新是异步且批量的原因解析 3. 函数式更新&#xff1a;唯一的正确写法4. 对比 Vue vs React 状态更新5. React useState 的核心源码…...

编程日记 2025/9/4 15:34:42

如何实现元素随滚动平滑上升

#技术栈Vue3TypeScript# 相比大家没少见过这个的效果&#xff1a; 作为视觉效果是很不错的 同时实现也很简单&#xff0c;本质是封装一个Vue指令 1&#xff0c;创建指令文件 src / directives / vSlidenIn.ts import type { Directive } from vueconst vSlideIn: Directive …...

编程日记 2025/8/29 16:54:42

Nginx部署spa单页面的小bug

没部署过&#xff0c;都是给后端干的&#xff0c;自己尝试部署了一个下午终于成功了 我遇到的最大的bug是进入后只有首页正常显示 其他页面全是404&#xff0c;于是问问问才知道&#xff0c;需要这个 location / { try_files $uri $uri/ /index.html; } 让…...

编程日记 2025/9/6 0:27:45

关于全球化大规模混合云 Kubernetes Prometheus 监控体系标准化及 GitOps 自动化改进方案

背景 现状 某司概况&#xff1a; PaaS/SaaS 公司&#xff0c;业务面向全球&#xff0c;包括 东南亚/南亚/中东/欧洲/非洲/美洲/东亚…生产 k8s 集群数十套&#xff0c;生产非生产 >100 套(多种集群类型&#xff0c;各种公有云/专有云/私有云/数据中心…)疫情以来&#xff…...

编程日记 2025/9/3 22:31:10

力扣DAY51 | 热100 | 岛屿数量

前言 中等 √ 做得我元气大伤&#xff0c;超级naive方法&#xff0c;新开辟一个数组存岛屿编号&#xff0c;一个数组存岛屿上的点。 题目 给你一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的的二维网格&#xff0c;请你计算网格中岛屿的数量。 …...

编程日记 2025/9/5 10:03:46

二叉树的最近公共祖先二叉搜索树的最近公共祖先

1 二叉树的最近公共祖先 学习&#xff1a; 代码 class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:if root is None or root is p or root is q:return rootleft self.lowestCommonAncestor(root.left,p,q)right …...

编程日记 2025/9/2 11:47:21

关于 LLB 的问题

This error occurs when you’re trying to run a program or library that was compiled with GLIBC (GNU C Library) version 2.29, but your system has an older version of GLIBC installed. Solutions: 1. Upgrade your system’s GLIBC (Recommended if possible) Fo…...

编程日记 2025/9/6 14:37:20

kafka4.0浅尝辄止

最近工作中接触消息队列比较多&#xff0c;前几周又看到kafka4.0发布&#xff0c;故写一篇博客对消息队列做一个复盘。 目录 消息队列对比1. Apache Kafka 4.02. RabbitMQ3. RocketMQ4. ActiveMQ5. Apache Pulsar6. NSQ kafka4.0鲜明的新特性Java 版本要求升级API 更新与精简移…...

编程日记 2025/9/2 17:51:06

nmcli创建wpa-psk2 wifi热点

1. 创建新的WiFi连接&#xff1a; sudo nmcli connection add type wifi ifname wlan0 con-name WiFi名称 autoconnect yes ssid WiFi名称 2. 配置接入点模式和IP共享&#xff1a; sudo nmcli connection modify WiFi名称 802-11-wireless.mode ap 802-11-wireless.band …...

编程日记 2025/9/2 1:07:38

分布式日志治理：Log4j2自定义Appender写日志到RocketMQ

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

编程日记 2025/9/2 17:50:49

【STM32单片机】#8 定时器编码器接口ADC模数转换器

主要参考学习资料&#xff1a; B站江协科技 STM32入门教程-2023版 细致讲解 中文字幕 开发资料下载链接&#xff1a;https://pan.baidu.com/s/1h_UjuQKDX9IpP-U1Effbsw?pwddspb 单片机套装&#xff1a;STM32F103C8T6开发板单片机C6T6核心板 实验板最小系统板套件科协 实验&…...

编程日记 2025/9/3 11:20:33

dify部署，ollama部署，拉取模型，创建ai聊天应用

dify下载安装 dify1.0.1 windos安装包百度云盘地址 通过网盘分享的文件&#xff1a;dify-1.0.1.zip 链接: 百度网盘 请输入提取码 提取码: 1234 dify安装包 linux安装包百度云盘地址 通过网盘分享的文件&#xff1a;dify-1.0.1.tar.gz 链接: 百度网盘 请输入提取码 提取码…...

编程日记 2025/9/1 21:51:51

213、【图论】有向图的完全联通（Python）

题目描述 原题链接&#xff1a;105. 有向图的完全联通 代码实现 import collectionsn, k list(map(int, input().split())) adjacency collections.defaultdict(list) for _ in range(k):head, tail list(map(int, input().split()))adjacency[head].append(tail)visited_…...

编程日记 2025/8/17 21:27:36

Node.js中util模块详解

Node.js 中 util 模块全部 API 详解 一、类型检查函数 const util require(util);// 1. util.types // 检查对象类型 console.log(util.types.isDate(new Date())); // true console.log(util.types.isRegExp(/abc/)); // true console.log(util.types.isArrayBuffer(new …...

编程日记 2025/8/17 19:49:02

BasicTS：全面基准测试与异质性分析

BasicTS&#xff1a;全面基准测试与异质性分析 在当今数字化时代&#xff0c;多元时间序列&#xff08;Multivariate Time Series, MTS&#xff09;分析在众多领域发挥着关键作用&#xff0c;从交通管理到能源系统优化&#xff0c;都离不开对MTS的精准预测。然而&#xff0c;当…...

编程日记 2025/8/31 21:43:04

认识python全栈框架reflex：快速打造工具类网站、模型调用web应用

以下是对reflex的简单介绍&#xff1a; 纯Python编写的&#xff0c;高性能、可自定义的 Web 应用开发框架 网页开发内置组件生态完整&#xff0c;灵活使用、快速接入、快速部署支持路由页面&#xff0c;可以开发复杂系统、企业级系统&#xff0c;这方面优于gradio、streamlit…...

编程日记 2025/9/2 17:26:15

课题申报的立项依据方位指南：使用DeepSeek提高课题立项的关键

在竞争日益激烈的学术研究和科研项目申报环境中&#xff0c;立项依据作为课题申报书的灵魂部分&#xff0c;往往决定着一项研究能否获得评审专家的青睐和资助。 然而&#xff0c;许多研究者尽管学术能力突出&#xff0c;却在立项依据的撰写上显得力不从心&#xff0c;导致优质…...

编程日记 2025/8/30 0:28:35

蓝桥杯电子赛_E2PROM（AT24C02）

目录 一 前言 二 E2PROM的相关讲解 AT24C02的地址 PCF8591的地址 三 根据提供的iic写代码 相关可能会有疑问的地方&#xff1a; 1 三个入口参数&#xff0c;都有什么用&#xff1f; 2 为什么在写中&#xff0c;要用IIC_SendByte&#xff0c;在读中&#xff0c;要用IIC_R…...

编程日记 2025/8/31 16:27:32

Kubernetes服务注册到consul流程实践

文章目录 前言架构图示意一、环境准备二、consul部署1.yaml示例2.consul部署验证 三、consulctl工具实现1.核心功能2.注册到consul的标签及元数据3.consulctl工具使用示例 四、通过Dockerfile构建consulctl工具镜像五、Kubernetes集成方案六、 结果验证1.注册验证2.销毁验证 总…...

编程日记 2025/9/4 19:06:17

供应链业务-供应链全局观（三）- 供应链三流的集成

概述 供应链的全局观的全两篇文章主要描述了供应链的基础概念和供应链的协作和集成问题。 供应链业务-供应链全局观&#xff08;一&#xff09;定义了什么是供应链和供应链管理。 所谓供应链就是把采购进来的东西&#xff0c;通过自身的生成加工&#xff0c;进行增值服务&am…...

编程日记 2025/9/3 10:54:55

Docker 提示Docker Engine stopped

做AI开发的时候&#xff0c;安装Docker提示Docker Engine stopped&#xff0c;以下是解决步骤&#xff1a; 一般都是成功的&#xff0c;不成功很可能是电脑兼容问题&#xff0c;通过采用4.4.4版本解决的&#xff1a; docker desktop 4.4.4 旧版本下载&#xff1a;在这里找到了4…...

编程日记 2025/9/5 18:41:53

对自己的优缺点评价

在面试中回答优缺点时&#xff0c;需要既体现自我认知的客观性&#xff0c;又能将优缺点与岗位需求结合&#xff0c;避免暴露可能影响工作的硬伤。以下是一个符合Java开发者角色的回答框架&#xff0c;供参考&#xff1a; 回答思路&#xff1a; 优点&#xff1a;选择与岗位直接…...

编程日记 2025/9/4 13:44:56

解决eNSP在24H2版本下AR_40启动失败问题

前言 1.网络学习中缺少不了模拟&#xff0c;自从Windows版本更新24H2以后&#xff0c;eNSP就出现各种问题&#xff0c;最常见的就是AR报错40【启动失败】&#xff0c;之前我也去网站搜了&#xff0c;也问了Microsoft社区&#xff0c;发现他们在底层逻辑上进行了修改(开启了虚拟…...

编程日记 2025/9/6 1:35:20

计算机组成原理-指令系统

1. 指令系统的定义与作用 指令系统&#xff08;Instruction Set Architecture, ISA&#xff09;是计算机硬件与软件之间的接口规范&#xff0c;定义了CPU能够识别和执行的所有指令的集合&#xff0c;是计算机体系结构的核心组成部分。 核心作用&#xff1a; 为程序员提供操作…...

编程日记 2025/9/5 18:07:12

Oracle数据库中 LEVEL start with prior connect by

在Oracle数据库中&#xff0c;处理层次结构数据是一项常见且重要的任务。无论是组织结构、分类目录还是其他具有层级关系的数据&#xff0c;Oracle都提供了强大的工具来简化和优化这些操作。其中&#xff0c;LEVEL伪列结合CONNECT BY和START WITH关键字&#xff0c;成为了处理层…...

编程日记 2025/9/4 1:19:20

HTTP 1.1 比 HTTP1.0 多了什么？（详尽版）

相较于HTTP 1.0&#xff0c;1.1 版本增加了以上特性&#xff1a; 1. 新增了连接管理即 keepalive&#xff0c;允许持久连接。 定义&#xff1a; Keepalive允许客户端和服务器在完成一次请求-响应后&#xff0c;保持连接处于打开状态&#xff0c;以便后续请求复用同一连接&am…...

编程日记 2025/9/3 4:51:55

Java学习手册：Java I/O与NIO

Java I/O&#xff08;Input/Output&#xff09;和NIO&#xff08;New Input/Output&#xff09;是Java语言中用于处理输入输出操作的重要部分。它们提供了丰富的API来处理文件和网络通信。I/O是Java早期版本中引入的&#xff0c;而NIO是在Java 1.4中引入的&#xff0c;旨在提供…...

编程日记 2025/9/2 3:57:55