用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…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
