用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…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
