用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…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
