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

Java数据结构与算法(0/1背包问题)

前言:

背包问题(Knapsack Problem)是组合优化问题中的一个经典问题,有多个变种。这里我们讨论的是 0/1 背包问题,这是最基本的一种形式。问题的描述如下:

给定 n 件物品,每件物品有一个重量 wi 和一个价值 vi,以及一个背包,它能够承载的最大重量为 W。我们需要确定应该将哪些物品放入背包,以使得背包内物品的总价值最大。

背包问题分类:

  • 0-1背包问题
  • 完全背包问题 
  • 多重背包问题
  • 混合背包问题
  • 二维背包问题
  • 分组背包问题
  • 有依赖的背包问题 (困难)

解题思路:

使用动态规划可以有效地解决 0/1 背包问题。动态规划的思想是将问题分解成子问题,并利用子问题的解来构建原问题的解。

  1. 定义状态:用 dp[i][j]表示前 i件物品恰好放入一个容量为 j的背包时所能获得的最大价值。
  2. 状态转移方程:        
  • 如果不选第 i件物品:dp[i][j]=dp[i−1][j]
  • 如果选第 i件物品:dp[i][j]=dp[i−1][j−wi]+vi
  • 综上:dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−wi]+vi)
  1. 初始条件:dp[0][j]=0对于所有的 j,即没有物品时的最大价值为 0。

实现代码

public class Knapsack {public static int knapsack(int W, int[] weights, int[] values, int n) {int[][] dp = new int[n + 1][W + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= W; w++) {if (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][W];}public static void main(String[] args) {int W = 50; // 背包容量int[] weights = {10, 20, 30}; // 物品重量int[] values = {60, 100, 120}; // 物品价值int n = values.length;System.out.println("最大价值: " + knapsack(W, weights, values, n));}
}

QA1:

相关文章:

Java数据结构与算法(0/1背包问题)

前言: 背包问题&#xff08;Knapsack Problem&#xff09;是组合优化问题中的一个经典问题&#xff0c;有多个变种。这里我们讨论的是 0/1 背包问题&#xff0c;这是最基本的一种形式。问题的描述如下&#xff1a; 给定 n 件物品&#xff0c;每件物品有一个重量 wi 和一个价值…...

LLVM 中 的 pass 及其管理机制

概述 LLVM 编译器框架的核心概念是任务调用和执行 编译器开发者将IR分解为不同的处理对象&#xff0c;并将其处理过程实现为单独的pass类型。在编译器初始化&#xff0c;pass被实例化&#xff0c;并被添加到pass管理中 pass 管理器(pass manager) 以流水线的方式将各个独立的…...

第 5 章 监控系统 | 入门案例 - 虚拟机监控

👉 本文目标:为 Linux 虚拟机/服务器安装 node_exporter,实现对虚拟机/服务器的监控。 👀 本文内容: 安装 Node Exporter,暴露 Linux 指标(比如 CPU、磁盘、IO 等)配置 Prometheus 抓取 Node Exporter 暴露的指标数据配置 Recording Rule,便于缓存/加速 Dashboard 频…...

教资认定报名照片要求小于190kb…

教资认定报名照片要求小于190kb…… 要求&#xff1a;文件小于190kb&#xff0c;宽度290-300&#xff0c;高度408-418 方法&#xff1a;vx搜随时照-教资认定 直接制作合规尺寸即可&#xff0c;还可以打印纸质版邮寄到家...

显示类控件——Calendar Widget

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 文章目录 一、Calendar Widget介绍核心属性重要信号代码示例: 获取选中的日期 一、Calendar Widget 介绍 …...

system与excel族函数区别

1.system #include<stdlib.h> int system(const char *command); comand是命令的路径&#xff0c;一般我们用绝对路径 system函数会创建新的进程&#xff0c;新的进程执行完返回原来的进程&#xff0c;原来的进程则继续执行后面的代码段。 如我们创建一个sys.cpp文件…...

STM32存储左右互搏 模拟U盘桥接SPI总线FATS读写FLASH W25QXX

STM32存储左右互搏 模拟U盘桥接SPI总线FATS读写FLASH W25QXX STM32的USB接口可以模拟成为U盘&#xff0c;通过FATS文件系统对连接的存储单元进行U盘方式的读写。 这里介绍STM32CUBEIDE开发平台HAL库模拟U盘桥接SPI总线FATS读写W25Q各型号FLASH的例程。 FLASH是常用的一种非易失…...

jrt从量变到质变

又是一个加班的周末&#xff0c;上周把台式机代码和数据库环境弄好了&#xff0c;这周进行大数据测试&#xff0c;直接把标本、标本医嘱、报告、报告结果、药敏结果等数据插入到1亿的规模&#xff0c;跑了一天一夜插入了5000多万个标本&#xff0c;后面接着补剩下的到一亿。 演…...

NLP主流大模型如GPT3/chatGPT/T5/PaLM/LLaMA/GLM的原理和差异有哪些-详细解读

自然语言处理&#xff08;NLP&#xff09;领域的多个大型语言模型&#xff08;如GPT-3、ChatGPT、T5、PaLM、LLaMA和GLM&#xff09;在结构和功能上有显著差异。以下是对这些模型的原理和差异的深入分析&#xff1a; GPT-3 (Generative Pre-trained Transformer 3) 虽然GPT-4…...

从MySQL到NoSQL:分析传统关系型数据库与NoSQL数据库的协同

引言 数据库是一个系统,用来管理和存储数据的地方。数据在数据库中以一种结构化的方式组织,这样能更容易地查询和处理数据。 关系型数据库是基于关系模型的数据库,它将数据存储在不同的表中,每个表都有各自的独一无二的主键。表与表之间通过共享的数据项相互关联。像MySQ…...

三、树和割集

文章目录 1、树1.1 树的定义1.2 树的性质1.3 极小连通图1.4 树的中心1.5 生成树1.5.1 最小生成树 2、 割点和桥THE END 1、树 1.1 树的定义 \qquad 定义&#xff1a; 一个连通的无圈的图称为树。 \qquad 只有一个顶点的树叫做平凡树。 \qquad 树中度为1的节点称为叶子结点。…...

泛型中<>和()中的类型

尖括号 < > 中的类型参数定义了一组可以被替换的类型占位符&#xff0c;而圆括号 (...) 内的类型使用则是这些类型参数的具体应用场景&#xff0c;展示了这些类型变量如何参与到函数的参数和返回值类型定义中去。这样设计既保证了代码的灵活性&#xff0c;又保持了类型安…...

spark mllib 特征学习笔记 (一)

PySpark MLlib 特征处理详解 PySpark MLlib 提供了丰富的特征处理工具&#xff0c;帮助我们进行特征提取、转换和选择。以下是 PySpark MLlib 中常用的特征处理类及其简要介绍。 1. Binarizer Binarizer 是将连续特征二值化的转换器。 from pyspark.ml.feature import Bina…...

SQLite 日期 时间

SQLite 日期 & 时间 SQLite 是一种轻量级的数据库管理系统&#xff0c;广泛用于各种应用程序中。它支持标准的 SQL 语法&#xff0c;包括对日期和时间的处理。在 SQLite 中&#xff0c;日期和时间可以通过几种不同的方式来存储和操作。 日期和时间数据类型 SQLite 使用 …...

飞书API 2-1:如何通过 API 创建文件夹?

本文探讨如何通过飞书的 API 来创建文件夹。通过 API 创建的文件夹&#xff0c;一般是放在共享空间&#xff0c;如果要放在个人空间&#xff0c;建议手动创建。 查看 API 文档 API 路径&#xff0c;可在飞书开放平台的服务端 API&#xff0c;依次查找云文档>云空间>文件…...

【APP移动端自动化测试】第一节.环境配置和adb调试工具

文章目录 前言一、Java环境搭建二、AndroidSDK环境搭建三、Android模拟器安装四、adb调试工具基本介绍 4.1 adb构成和基本原理 4.2 adb获取包名&#xff0c;界面名 4.3 adb文件传输 4.4 adb获取app启动时间 4.5 adb获取手机日志 4.6 adb其他有关…...

Kotlin 协程:从基础概念到开发实践

前言 上一篇文章 深入理解Android多线程开发:场景应用与解决方案解析 针对Android开发中的多线程应用场景和相应的解决方案做了一个梳理。 总结出了Android开发中多线程编程的几个重要点: 资源复用和优化切线程任务编排并结合示例说明了Kotlin协程在处理上述问题时的优势。 …...

IPNV6

特征——升级点&#xff1a; 1、全球单播地址 ----IPV4地址下的公有地址 V6下没 nat 2、可聚合性 (IANA组织对全球的地址进行合理分配) 3、多宿主——一个物理接口可以同时拥有多个不同网段的IPV6地址&#xff1b;但不同接口不能在同一网段 4、自动配置 1&#xff…...

C++并发之锁(std::lock_guard,std::unique_lock)

目录 1 概述2 使用实例3 接口使用3.1 lock_guard3.2 adopt_lock3.3 defer_lock3.4 try_to_lock3.5 try_lock3.6 release3.7 lock3.8 call_one1 概述 锁保护是通过使互斥对象始终处于锁定状态来管理互斥对象的对象。。   在构造时,互斥对象被调用线程锁定,在析构时,互斥被解…...

FreeRTOS队列(queue)

队列(queue)可以用于"任务到任务"、 "任务到中断"、 "中断到任务"直接传输信息。 1、队列的特性 1、1常规操作 队列的简化操如下图所示&#xff0c;从此图可知&#xff1a; 队列中可以包含若干数据&#xff1a;队列中有若干项&#xff0c;这…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...