当前位置: 首页 > news >正文

动态规划 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]);}}}}

相关文章:

动态规划 01背包(算法)

现有四个物品&#xff0c;小偷的背包容量为8&#xff0c;怎么可以偷得价值较多的物品 如: 物品编号&#xff1a; 1 2 3 4 物品容量&#xff1a; 2 3 4 5 物品价值&#xff1a; 3 4 5 8 记f(k,w) ,当背包容量为w,可以偷k件物品…...

使用常数指针作为函数参数

在main.cpp里输入程序如下&#xff1a; #include <iostream> //使能cin(),cout(); #include <iomanip> //使能setbase(),setfill(),setw(),setprecision(),setiosflags()和resetiosflags(); //setbase( char x )是设置输出数字的基数,如输出进制数则用setbas…...

wps宏代码学习

推荐学习视频&#xff1a;https://space.bilibili.com/363834767/channel/collectiondetail?sid1139008&spm_id_from333.788.0.0 打开宏编辑器和JS代码调试 工具-》开发工具-》WPS宏编辑器 左边是工程区&#xff0c;当打开多个excel时会有多个&#xff0c;要注意不要把…...

libavdevice.so.58: cannot open shared object file: No such file ordirectory踩坑

博主是将大图切分成小图时遇到 问题一、linux编译后&#xff0c;找不到ffmpeg中的一个文件 产生原因&#xff0c;各种包集成&#xff0c;然后安装以后乱七八糟&#xff0c;甚至官方的教程也不规范导致没有添加路径到系统文件导致系统执行的时候找不到 1.下载 博主进行的离线…...

Rust:Vec<u8> 与 [u8] 之间的转换

在 Rust 中&#xff0c;Vec<u8> 是一个动态数组&#xff0c;而 &[u8] 是一个指向字节切片的不可变引用。这两者之间经常需要进行转换&#xff0c;因为它们在处理字节数据时非常常见。 从 &[u8] 转换为 Vec<u8> 要将一个字节切片 &[u8] 转换为一个 Ve…...

Leetcode 课程表

这段代码的算法思想是基于**深度优先搜索&#xff08;DFS&#xff09;**来检测图中的环路&#xff0c;从而判断是否可以完成所有课程。具体来说&#xff0c;我们将每门课程和它的先修关系视为一个有向图&#xff0c;问题的核心就是判断这个有向图中是否存在环路。如果有环路&am…...

Java面试经典 150 题.P55. 跳跃游戏(009)

本题来自&#xff1a;力扣-面试经典 150 题 面试经典 150 题 - 学习计划 - 力扣&#xff08;LeetCode&#xff09;全球极客挚爱的技术成长平台https://leetcode.cn/studyplan/top-interview-150/ 题解&#xff1a; class Solution {public boolean canJump(int[] nums) {int…...

登录的时候密码使用crypto-js加密解密

首先要下载插件 npm install crypto-js 然后新建一个js文件 crypto.js // 导入 CryptoJS 模块 import CryptoJS from crypto-js; const secretKey"pZsgDSvzaeHWDkhLDxvrrrYvBlAsIHmZ";//一般是后端提供的 /*** description: 加解密函数* param {*} data 需要加密的数…...

LLM大模型部署实战指南:部署简化流程

LLM大模型部署实战指南:Ollama简化流程,OpenLLM灵活部署,LocalAI本地优化,Dify赋能应用开发 1. Ollama 部署的本地模型(🔺) Ollama 是一个开源框架,专为在本地机器上便捷部署和运行大型语言模型(LLM)而设计。,这是 Ollama 的官网地址:https://ollama.com/ 以下是其…...

24年10月Google Play政策更新通知

今天gmail邮箱里收到了google play最新的政策更新通知&#xff0c;这次的通知对于我来说&#xff0c;影响不大&#xff0c;邮件内容主要分为三部分。 一、政策更新部分 这里更新的政策只有医疗功能相关的。针对健康和医疗应用增加了最新的医疗指南和免责声明要求&#xff0c;并…...

玄机-应急响应- Linux入侵排查

一、web目录存在木马&#xff0c;请找到木马的密码提交 到web目录进行搜索 find ./ type f -name "*.php" | xargs grep "eval(" 发现有三个可疑文件 1.php看到密码 1 flag{1} 二、服务器疑似存在不死马&#xff0c;请找到不死马的密码提交 被md5加密的…...

数据驱动业务中的BDS对账班牛返款表集成方案

数据驱动业务中的BDS对账班牛返款表集成方案 BDS对账班牛返款表_update&#xff1a;班牛数据集成到MySQL的技术实现 在数据驱动的业务环境中&#xff0c;如何高效、准确地将分散在不同系统中的数据进行整合&#xff0c;是每个企业面临的重要挑战。本文将分享一个具体的技术案例…...

【Kubernetes实战】三、资源组件Namespace、Pod、Label、Deployment、Service概述。

目录 1. Namespace1) namespace作用2) namespace资源的具体操作 2. Pod1) Pod概述2) Pod资源的具体操作 3. Label1) Label概述2) Label资源的具体操作 4. Deployment1) Deployment概述2) Deployment控制器的具体操作 5. Service1) Service概述2) Service资源的具体操作 1. Name…...

去中心化的模型训练

去中心化的模型训练&#xff08;Decentralized Model Training&#xff09;是一种不依赖单一中心服务器或数据存储中心&#xff0c;而是在多个节点&#xff08;如设备或数据拥有者&#xff09;上进行联合训练的方法。这种训练模式可以更好地保护数据隐私、降低数据传输成本&…...

Arthas调试线上代码技巧

1、Arthas概述 官网地址&#xff1a;https://arthas.aliyun.com/ 下载地址&#xff1a;https://arthas.aliyun.com/arthas-boot.jar 使用教程&#xff1a;https://arthas.aliyun.com/doc/quick-start.html Arthas&#xff08;阿尔萨斯&#xff09;是 Alibaba 开源的一款Java诊断…...

QT访问数据库:应用提示Driver not loaded

在QT中运行完全正确错误截图 解决办法1 我用的是MySQL。我把libmysql.dll复制到应用程序的目录下&#xff0c;即可正常访问数据库。 解决办法2 bool open_work_db() {QString info "support drivers:";for (int i0; i<QSqlDatabase::drivers().size(); i){inf…...

支持ANC的头戴式蓝牙耳机,更有小金标认证,QCY H3 Pro体验

平时听音乐、看视频&#xff0c;大家都想获得更悦耳的音质体验&#xff0c;这时候蓝牙耳机就是性价比更高的一种方案&#xff0c;同时因其无线束缚、便携性高的特点&#xff0c;随时拿出来就能用。更不用说如今国产品牌的蓝牙耳机升级迭代速度非常快&#xff0c;百元的价位就可…...

net framework 3.5组件更新失败错误代码0x80072f8f怎样解决

浏览器地址栏输入www.dnz9.com远程解决netframework问题 当遇到.NET Framework 3.5 组件更新失败&#xff0c;错误代码为 0x80072f8f 时&#xff0c;可以尝试以下几种解决方法&#xff1a; 一、检查网络连接和时间设置 网络连接 错误代码 0x80072f8f 通常与网络相关问题有关。首…...

C语言初阶:十一.代码调试技巧

❤欢迎各位大佬访问&#xff1a;折枝寄北-CSDN博客折枝寄北擅长C语言初阶,等方面的知识,折枝寄北关注python,c,java,qt,c语言领域.https://blog.csdn.net/2303_80170533?typeblog❤文章所属专栏https://blog.csdn.net/2303_80170533/category_12794764.html?spm1001.2014.300…...

Jenkins Pipeline 部署总结

Jenkins Pipeline 部署总结 前言 Jenkins Pipeline 是 Jenkins 提供的一套强大的工作流框架&#xff0c;它允许开发者以代码的形式定义整个软件交付过程&#xff0c;从而实现持续集成和持续部署&#xff08;CI/CD&#xff09;。通过 Pipeline&#xff0c;原本独立运行于单个或…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...