用Java实现01背包问题 用贪心算法
贪心算法不是解决01背包问题的有效方法,因为贪心算法只能保证得到一个近似最优解,而无法保证得到最优解。因此,我们需要使用动态规划来解决01背包问题。以下是使用Java实现的动态规划解法:
public class KnapsackProblem {public static int knapSack(int W, int[] wt, int[] val, int n) {int[][] dp = new int[n + 1][W + 1];for (int i = 0; i <= n; i++) {for (int w = 0; w <= W; w++) {if (i == 0 || w == 0) {dp[i][w] = 0;} else if (wt[i - 1] <= w) {dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][W];}public static void main(String[] args) {int[] val = {60, 100, 120};int[] wt = {10, 20, 30};int W = 50;int n = val.length;System.out.println(knapSack(W, wt, val, n)); // 输出220}
}
在上述代码中,我们使用一个二维数组dp来表示当前背包容量和物品数量下的最大价值。初始化时,将数组中的所有元素置为0。然后,使用两个嵌套循环来遍历所有可能的背包容量和物品数量的组合。在每个位置,我们根据当前物品的重量和价值来更新最大价值。最后,返回dp[n][W]即为问题的解。
相关文章:
用Java实现01背包问题 用贪心算法
贪心算法不是解决01背包问题的有效方法,因为贪心算法只能保证得到一个近似最优解,而无法保证得到最优解。因此,我们需要使用动态规划来解决01背包问题。以下是使用Java实现的动态规划解法: public class KnapsackProblem {public…...
JUC并发编程-8锁现象
5. 8锁现象 如何判断锁的是谁!锁到底锁的是谁? 锁会锁住:对象、Class 深刻理解我们的锁 问题1 两个同步方法,先执行发短信还是打电话 public class dome01 {public static void main(String[] args) {Phone phone new Phon…...
集美大学“第15届蓝桥杯大赛(软件类)“校内选拔赛 D矩阵选数
经典的状态压缩DP int dp[15][(1<<14)10]; int a[15][15]; void solve() {//dp[i][st]考虑到了第i行 并且当前考虑完第i行以后的选择状态是st的所有方案中的最大值for(int i1;i<13;i)for(int j1;j<13;j)cin>>a[i][j];for(int i1;i<13;i){for(int j0;j<…...
Android System Service系统服务--1
因为工作中经常需要解决一些framework层的问题,而framework层功能一般都是system service 的代理stub,然后封装相关接口,并提供给APP层使用,system service则在不同的进程中运行,这样实现了分层,隔离&#…...
【RT-DETR有效改进】华为 | Ghostnetv1一种专为移动端设计的特征提取网络
前言 大家好,这里是RT-DETR有效涨点专栏。 本专栏的内容为根据ultralytics版本的RT-DETR进行改进,内容持续更新,每周更新文章数量3-10篇。 专栏以ResNet18、ResNet50为基础修改版本,同时修改内容也支持ResNet32、ResNet101和PP…...
45个经典Linux面试题!赶紧收藏!
问题一: 绝对路径用什么符号表示?当前目录、上层目录用什么表示?主目录用什么表示? 切换目录用什么命令? 答案:绝对路径:如/etc/init.d当前目录和上层目录:./ …/主目录:~/切换目…...
将字符串中可能被视为正则表达式的特殊字符进行转义re.escape()
【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 将字符串中可能被视为 正则表达式的特殊字符 进行转义 re.escape() [太阳]选择题 请问以下代码最后输出的结果是? import re s [a-z] print("【显示】s ",s) print(&q…...
C语言:函数指针的使用
在C语言中,函数指针是指向函数的指针变量。它可以存储函数的地址,使得可以通过该指针来调用函数。以下是函数指针的基本概念和用法: 一、基本概念: 声明函数指针: returnType (*pointerName)(parameterTypes); 这里 r…...
「实战应用」如何用DHTMLX Gantt构建类似JIRA式的项目路线图(二)
DHTMLX Gantt是用于跨浏览器和跨平台应用程序的功能齐全的Gantt图表。可满足项目管理应用程序的所有需求,是最完善的甘特图图表库。 在web项目中使用DHTMLX Gantt时,开发人员经常需要满足与UI外观相关的各种需求。因此他们必须确定JavaScript甘特图库的…...
Webpack5入门到原理18:Plugin 原理
Plugin 的作用 通过插件我们可以扩展 webpack,加入自定义的构建行为,使 webpack 可以执行更广泛的任务,拥有更强的构建能力。 Plugin 工作原理 webpack 就像一条生产线,要经过一系列处理流程后才能将源文件转换成输出结果。 这条…...
PWM之舵机
舵机又称直流电机,如下图 本节承接上节,具体的PWM技术已经在上一节讲的很详细了,本节就不再讲了,那么我们的重点就放在直流电机的工作原理上了。 一、工作原理 我们研究直流电机,主要式研究直流电机旋转速度的调节&a…...
Python并发与多线程:IO并发(阻塞IO、非阻塞IO、IO多路复用、异步IO)
在Python中,有多种处理并发的方式,其中之一就是使用多线程进行IO并发操作。在IO操作中,有四种常见的方式:阻塞IO、非阻塞IO、IO多路复用和异步IO。 阻塞IO(Blocking IO):当执行一个IO操作时&…...
React16源码: React中的IndeterminateComponent的源码实现
IndeterminateComponent 1 )概述 这是一个比较特殊的component的类型, 就是还没有被指定类型的component在一个fibrer被创建的时候,它的tag可能会是 IndeterminateComponent在 packages/react-reconciler/src/ReactFiber.js 中,有…...
SpringBoot:详解Bean生命周期和作用域
🏡浩泽学编程:个人主页 🔥 推荐专栏:《深入浅出SpringBoot》《java项目分享》 《RabbitMQ》《Spring》《SpringMVC》 🛸学无止境,不骄不躁,知行合一 文章目录 前言一、生命周期二…...
【图解数据结构】顺序表实战指南:手把手教你详细实现(超详细解析)
🌈个人主页:聆风吟 🔥系列专栏:图解数据结构、算法模板 🔖少年有梦不应止于心动,更要付诸行动。 文章目录 一. ⛳️线性表1.1 🔔线性表的定义1.2 🔔线性表的存储结构 二. ⛳️顺序表…...
WordPress怎么禁用文章和页面古腾堡块编辑器?如何恢复经典小工具?
现在下载WordPress最新版来搭建网站,默认的文章和页面编辑器,以及小工具都是使用古腾堡编辑器(Gutenberg块编辑器)。虽然有很多站长说这个编辑器很好用,但是仍然有很多站长用不习惯,觉得操作太难了…...
【HarmonyOS】掌握布局组件,提升应用体验
从今天开始,博主将开设一门新的专栏用来讲解市面上比较热门的技术 “鸿蒙开发”,对于刚接触这项技术的小伙伴在学习鸿蒙开发之前,有必要先了解一下鸿蒙,从你的角度来讲,你认为什么是鸿蒙呢?它出现的意义又是…...
第4周:Pytorch——综合应用和实战项目 Day 28-30: 学习资源和社区参与
第4周:综合应用和实战项目 Day 28-30: 学习资源和社区参与 在这个阶段,我们将探索更多的学习资源并鼓励参与PyTorch和TensorFlow的社区,以进一步提升技术和融入开发者社群。 学习资源: 论文:阅读最新的机器学习和深度…...
TypeScript教程(一)在vscode中的配置TypeScript环境
TypeScript教程(一)在vscode中的配置TypeScript环境 文章目录 TypeScript教程(一)在vscode中的配置TypeScript环境一、前言二、具体步骤1、Node.js安装2、TypeScript安装3、helloworld 一、前言 未来的开发者们请上座,…...
sshpass的安装与使用
一.简介 1.定义: ssh 登陆不能在命令行中指定密码,sshpass 的出现则解决了这一问题。它允许你用 -p 参数指定明文密码,然后直接登录远程服务器,它支持密码从命令行、文件、环境变量中读取。 2.使用 sshpass 原因 使用 sshpass…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
