动态规划 01背包(算法)

现有四个物品,小偷的背包容量为8,怎么可以偷得价值较多的物品

如:

物品编号: 1     2      3      4 

物品容量: 2     3      4      5

物品价值: 3     4      5      8

记f(k,w) ,当背包容量为w,可以偷k件物品,所能偷到的最大价值

以f(4,8)为列,记录每次偷取物品有两种情况 偷//不偷,如果偷取出物品的价值并减少对应背包的容量,如果不偷,则不需要取出价值,也不需要减去对应的容量, 依次找到偷取物品为0个,或者容量不够时为止。

由上述递推可得下面公式

 

 

 

代码实现:

 

package 算法;public class 背包 {public static void main(String[] args) {int[][] f = new int[5][9];int[] w = new int[]{0, 2, 3, 4, 5};int[] v = new int[]{0, 3, 4, 5, 8};for (int i = 1; i < 5; i++) {for (int j = 1; j < 9; j++) {if (w[i] > j) {f[i][j] = f[i - 1][j];} else {f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);}}}for (int i = 0; i < 5; i++) {for (int j = 0; j < 9; j++) {System.out.println(i+" "+j+" "+f[i][j]);}}}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463868.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

引领数字时代:万码优才如何变革IT人才招聘新体验(这里有更精准的推荐)

目录 引领数字时代&#xff1a;万码优才如何变革IT人才招聘新体验引领未来科技&#xff0c;精准链接IT精英精准匹配&#xff0c;高效对接海量资源&#xff0c;覆盖广泛优化体验&#xff0c;简化流程 全面升级&#xff1a;AI赋能数字人才职业成长AI模拟面试职场千问智能简历评估…

Rocky Linux 9安装后无法远程ssh密码登录解决

在Rocky Linux 9版本中&#xff0c;为了增加安全性&#xff0c;默认情况下禁用SSH root密码登录。这是系统默认设定的规则&#xff0c;我们同样也可以更改它。   允许Rocky Linux 9 root用户通过ssh登录方法&#xff1a; 1.编辑SSH配置文件 2.找到以下内容 PermitRootLogin …

1.2 图像处理基本操作

在本实战中&#xff0c;我们将学习如何使用OpenCV进行基本的图像处理操作。首先&#xff0c;我们将通过cv2.imread()函数读取图像&#xff0c;并使用cv2.imshow()在窗口中显示它。接着&#xff0c;我们将探索如何通过cv2.imwrite()保存图像&#xff0c;并设置不同的参数以控制图…

【C++】哈希表模拟:开散列技术与哈希冲突处理

C语法相关知识点可以通过点击以下链接进行学习一起加油&#xff01;命名空间缺省参数与函数重载C相关特性类和对象-上篇类和对象-中篇类和对象-下篇日期类C/C内存管理模板初阶String使用String模拟实现Vector使用及其模拟实现List使用及其模拟实现容器适配器Stack与QueuePriori…

「Mac畅玩鸿蒙与硬件18」鸿蒙UI组件篇8 - 高级动画效果与缓动控制

高级动画可以显著提升用户体验&#xff0c;为应用界面带来更流畅的视觉效果。本篇将深入介绍鸿蒙框架的高级动画&#xff0c;包括弹性动画、透明度渐变和旋转缩放组合动画等示例。 关键词 高级动画弹性缓动自动动画缓动曲线 一、Animation 组件的高级缓动曲线 缓动曲线&#…

SpringBoot源码解析(二):启动流程之引导上下文DefaultBootstrapContext

SpringBoot源码系列文章 SpringBoot源码解析(一)&#xff1a;启动流程之SpringApplication构造方法 SpringBoot源码解析(二)&#xff1a;启动流程之引导上下文DefaultBootstrapContext 目录 前言一、入口二、DefaultBootstrapContext1、BootstrapRegistry接口2、BootstrapCon…

ELK之路第三步——日志收集筛选logstash和filebeat

logstash和filebeat&#xff08;偷懒版&#xff09; 前言logstash1.下载2.修改配置文件3.测试启动4.文件启动 filebeat1.下载2.配置3.启动 前言 上一篇&#xff0c;我们说到了可视化界面Kibana的安装&#xff0c;这一篇&#xff0c;会简单介绍logstash和filebeat的安装和配置。…

Python毕业设计选题:基于Hadoop的租房数据分析系统的设计与实现

开发语言&#xff1a;Python框架&#xff1a;flaskPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 系统首页 房屋信息详情 个人中心 管理员登录界面 管理员功能界面 用户管理界面 房屋信…

深度学习笔记之BERT(一)BERT的基本认识

深度学习笔记之BERT——BERT的基本认识 引言回顾&#xff1a;Transformer的策略回顾&#xff1a;Word2vec的策略和局限性 BERT \text{BERT} BERT的基本理念抽象的双向BERT的预训练策略 预训练与微调 引言 从本节开始&#xff0c;将介绍 BERT \text{BERT} BERT系列模型以及其常…

YOLOv8改进,YOLOv8引入ResCBAM注意力机制,二次创新C2f结构

摘要 腕部创伤甚至骨折在日常生活中经常发生,在儿童中,他们占骨折病例的很大比例。在进行手术之前,外科医生通常会要求患者先进行 X 光成像,并根据放射科医生的分析进行手术准备。随着神经网络的发展,“You Only Look Once”(YOLO)系列模型在骨折检测中的应用越来越广泛…

CSS--两列网页布局,三列布局和多行多列布局

两列网页布局 两列网页布局实验 先将一个未运用浮动效果的网页结构写出来 <style>header{/* 给页眉设置宽高和样式 */width:1000px;height: 40px;background-color: gray;border: 3px brown solid;margin-bottom: 5px;}article{width:1000px;height: 600px;background-c…

如何使用Web-Check和cpolar实现安全的远程网站监测与管理

文章目录 前言1.关于Web-Check2.功能特点3.安装Docker4.创建并启动Web-Check容器5.本地访问测试6.公网远程访问本地Web-Check7.内网穿透工具安装8.创建远程连接公网地址9.使用固定公网地址远程访问 前言 本期给大家分享一个网站检测工具Web-Check&#xff0c;能帮你全面了解网…

Webserver(2.6)信号

目录 信号的概念信号相关的函数killraiseabortalarm1s钟电脑能数多少个数&#xff1f; setitimer过3s以后&#xff0c;每隔2s定时一次 信号捕捉函数signalsigaction 信号集sigprocmask编写一个程序&#xff0c;把所有的常规信号未决状态打印到屏幕 sigchld信号 信号的概念 比如…

AprilTag在相机标定中的应用简介

1. AprilTag简介 相机标定用的标靶类型多样,常见的形式有棋盘格标靶和圆形标靶。今天要介绍的AprilTag比较特别,它是一种编码形式的标靶。其官网为AprilTag,它是一套视觉基准系统,包含标靶编解码方法(Tag生成)和检测算法(Tag检测),可用于AR、机器人、相机标定等领域。…

Qt报错QOCI driver not loaded且QOCI available的解决方法

参考 Linux Qt 6安装Oracle QOCI SQL Driver插件&#xff08;适用WSL&#xff09; 安装 QOCI 插件完成后运行 Qt 项目报错&#xff1a; qt.sql.qsqldatabase: QSqlDatabase: QOCI driver not loaded qt.sql.qsqldatabase: QSqlDatabase: available drivers: QMIMER QPSQL QODBC…

【MySQL】 穿透学习数据库理论与知识剖析

前言&#xff1a;本节内容讲述一些数据库的基本概念。 第一个部分就是数据库相关的概念&#xff0c; 比如什么是数据库&#xff0c; 如何理解mysqld以及mysql。第二部分理解数据库和表在系统层面的形式。 第三部分就是mysql的一些操作分类。 第四部分就是数据库的插件配置这些。…

Web Broker(Web服务应用程序)入门教程(1)

1、介绍 Web Broker 组件&#xff08;位于工具面板的“Internet”选项卡中&#xff09;可以帮助您创建与特定统一资源标识符&#xff08;URI&#xff09;相关联的事件处理程序。当处理完成后&#xff0c;您可以通过编程方式构建 HTML 或 XML 文档&#xff0c;并将它们传输给客…

网络安全法详细介绍——爬虫教程

目录 [TOC](目录)一、网络安全法详细介绍1. 网络安全法的主要条款与作用2. 网络安全法与爬虫的关系3. 合法使用爬虫的指南 二、爬虫的详细教程1. 准备环境与安装工具2. 使用requests库发送请求3. 解析HTML内容4. 使用robots.txt规范爬虫行为5. 设置请求间隔6. 数据清洗与存储 三…

25国考照片处理器使用流程图解❗

1、打开“国家公务员局”网站&#xff0c;进入2025公务员专题&#xff0c;找到考生考务入口 2、点击下载地址 3、这几个下载链接都可以 4、下载压缩包 5、解压后先看“使用说明”&#xff0c;再找到“照片处理工具”双击。 6、双击后会进入这样的界面&#xff0c;点击&…

Go 语言之搭建通用 Web 项目开发脚手架

Go 语言之搭建通用 Web 项目开发脚手架 MVC 模式 MVC 模式代表 Model-View-Controller&#xff08;模型-视图-控制器&#xff09; 模式。这种模式用于应用程序的分层开发。 Model&#xff08;模型&#xff09; - 模型代表一个存取数据的对象或 JAVA POJO。它也可以带有逻辑&…