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

【动态规划】0-1背包问题

【动态规划】0-1背包问题

题目:现在有四个物品,背包总容量为8,背包最多能装入价值为多少的物品?

我的图解

表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。

拿a【1】【1】来说,它的值就是背包容量为1,只考虑编号0,1的物品时,背包所能装入的最大价值;

然后既然是动态规划,那就一定有初值,也就是a【0】【j】 = 0; a【i】【0】 = 0;即第一行和第一列都为0;


然后根据初值来推后面的值;

首先要判断本行所对应的物品是否能装入背包,

拿a【1】【1】来说,首先要判断,若只考虑编号为1的物品,它是否可以装入背包,此时的背包容量为1,而编号为1的物品的体积为2,故它无法装入背包,那么a【1】【1】的值和背包容量为1,只考虑编号为0的物品时,背包所能装入的最大价值(即a【0】【1】)是相等的;

若能装入背包;那么有两种选择:

(1)装入本行物品,即先装入本行的物品,然后剩下背包容量装其他价值之和最大的物品

(2)不装本行物品,即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品)
然后比较(1)(2)选择较大者;


拿a【2】【4】来说,此时的背包容量为4,编号为2的物品的体积为3,故2号物品能装入背包,然后两种选择:
(1)装入2号物品,此时背包剩余容量为1,此时只剩下两个物品,那就是编号为0和1的物品,查表得a【1】【1】=0

故此时的最大价值为a【1】【1】加上2号物品的价值,也就是4

(2)不装2号物品,即背包容量都用来装除了本行物品之外的其他物品(即本行前面几行的物品)
由于不装入2号物品,此时的最大价值和只考虑编号为0,1物品,背包容量为4的情况的最大价值(即a【1】【4】)是相等的,
也就是3;

故选择(1)(2)中较大者,a【2】【4】=4;

依次类推下去。

解法归纳:

一、如果装不下当前物品,那么前n个物品的最佳组合和前n-1个物品的最佳组是一
样的。

二、如果装得下当前物品。

假设1:装当前物品,在给当前物品预留了相应空间的情况下,前n-1 个物品的最佳组
合加上当前物品的价值就是总价值。

假设2:不装当前物品,那么前n个物品的最佳组合和前n-1个物品的最佳组合是一样
的。

选取假设1和假设2中较大的价值,为当前最佳组合的价值。


代码实现

package eunm.Try;//0-1背包问题
public class BB {public static void main(String[] args) {// TODO 自动生成的方法存根int volume[] = {2, 3, 4, 5};int value[] = {3, 4, 5, 6};int maxvolume = 9;System.out.println(knapsack(volume, value, maxvolume));}public static int knapsack(int[] volume, int[] value, int maxvolume) {int n = volume.length;//最大价值数组为maxvalue[N+1][maxvolume+1],因为我们要从0开始保存int[][] maxvalue = new int[n + 1][maxvolume + 1];//体积和物品为0时,价值为0for (int j = 0; j < maxvolume + 1; j++) {maxvalue[0][j] = 0;}for (int i = 0; i < n + 1; i++) {maxvalue[i][0] = 0;}//i:只拿前i件物品(这里的i因为取了0,所以对应到weight和value里面都是i-1号位置)//j:假设能取的总体积为j//n是物品件数for (int i = 1; i <= n; i++) {for (int j = 1; j <= maxvolume; j++) {//当前最大价值等于放上一件的最大价值maxvalue[i][j] = maxvalue[i - 1][j];//如果当前件的体积小于总体积,可以放进去或者拿出别的东西再放进去if (volume[i - 1] <= j) {/*比较(不放这个物品的价值)和(这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]时取前i-1个物品时的对应体积时候的最高价值)maxvalue[i - 1][j - volume[i - 1]]的大小*/if (value[i - 1] + maxvalue[i - 1][j - volume[i - 1]] > maxvalue[i - 1][j]) {maxvalue[i][j] = value[i - 1] + maxvalue[i - 1][j - volume[i - 1]];}}}}return maxvalue[n][maxvolume];}}

这里比较关键。

//如果当前件的体积小于总体积,可以放进去或者拿出别的东西再放进去if (volume[i - 1] <= j) {/*比较(不放这个物品的价值)和(这个物品的价值value[i - 1] 加上 当前能放的总体积减去当前物品体积j - volume[i - 1]时取前i-1个物品时的对应体积时候的最高价值)maxvalue[i - 1][j - volume[i - 1]]的大小*/if (value[i - 1] + maxvalue[i - 1][j - volume[i - 1]] > maxvalue[i - 1][j]) {maxvalue[i][j] = value[i - 1] + maxvalue[i - 1][j - volume[i - 1]];}}

背包问题回溯:在使得背包内总价值最大的情况下,背包内装了哪些物品?

这里我暂时不想研究了呜呜脑阔疼。


再来一个今天做的题目:小明是一个大胖子,为了让体重达到正常水平,他的计划是:减掉n千克体重,分多周完成(至少是2周),每周都减重正整数千克。为了激励自己,他决定每周减掉的体重都必须比上周减掉的体重多。假设他上周减重0千克,他从这周开始执行计划,请问可以设计出多少种方案?

套一下上面的模板就行。

package Excepect;import java.util.Scanner;public class AAAA {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();long[][] dp = new long[n][n + 1];dp[0][0] = 1;for (int i = 1; i < n; i++) {//i表示接收体重后体重变化dp[i][0] = 1;//第一周开始减最少从1开始for (int j = 1; j <= n; j++) {//j表示能减的总体重//当前方案=上一体重的方案dp[i][j] = dp[i - 1][j];//如果当前体重<=能减的总体重if (i <= j) {//最多总方案=现有方案+(能减的总体重-当前体重时取前i-1对应体重的最多总方案)dp[i][j] = dp[i][j] + dp[i - 1][j - i];}}}System.out.println(dp[n - 1][n]);scan.close();}
}

突然发现学算法真的很费脑子。。。。。。最近两天家里面在干活,我不仅时刻被叫去帮忙干活还要去帮忙做午饭,没办法农村家庭里的孩子就是这么命苦呜呜呜,所以就没办法专注下来学习,断断续续的。

不过总结确实是一件好事,不总结的话我可能都学不懂什么。前天晚上弄的那个个人博客吧,就如同我朋友说的一样,我像极了瞎猫碰见死耗子,到处乱碰,看看碰到了没。。。

然后一直搞到深夜十二点半才在我的博客主页看到了我写的文章。目前还没成功,还没把博客部署到服务器上,好像就是差这一步来着。等我搞好了我会写一篇技术文的嘿嘿嘿。

本文由mdnice多平台发布

相关文章:

【动态规划】0-1背包问题

【动态规划】0-1背包问题 题目:现在有四个物品&#xff0c;背包总容量为8&#xff0c;背包最多能装入价值为多少的物品? 我的图解 表格a【i】【j】表示的是容量为j的背包装入前i个物品的最大价值。 拿a【1】【1】来说&#xff0c;它的值就是背包容量为1&#xff0c;只考虑…...

WordPress 高级缓存插件 W3 Total Cache Pro 详细配置教程

说起来有关 WordPress 缓存插件明月已经发表过不少文章了,但有关 W3 Total Cache Pro 这个 WordPress 高级缓存插件除了早期【网站缓存插件 W3 Total Cache,适合自己的才是最好的!】一文后就很少再提及了,最近因为明月另一个网站【玉满斋】因为某些性能上的需要准备更换缓存…...

每日一题——Python实现PAT乙级1012 数字分类(举一反三+思想解读+逐步优化)五千字好文

一个认为一切根源都是“自己不够强”的INTJ 个人主页&#xff1a;用哲学编程-CSDN博客专栏&#xff1a;每日一题——举一反三Python编程学习Python内置函数 Python-3.12.0文档解读 目录 我的写法 代码优点 代码缺点 时间复杂度 空间复杂度 代码改进建议 我要更强 哲…...

Unity2D游戏制作入门 | 13 ( 之人物三段攻击 )

上期链接&#xff1a;Unity2D游戏制作入门 | 12(之人物受伤和死亡的逻辑动画)-CSDN博客 上期我们聊了人物的受伤和死亡的逻辑和动画&#xff0c;我们主要学习了事件的执行&#xff0c;即我们在人物受伤时可能会触发很多的事件&#xff0c;比如触发人物受伤的动画以及播放音乐等…...

DAY04 HTMLCSS

文章目录 一 表单(1) 数字控件(2) 颜色控件(3) 日期控件(4) 月份控件(5) 星期控件(6) 搜索控件(7) 范围控件 二 浮动框架三 结构化标签四 CSS1 CSS概述2 CSS的编写位置1. inline style 行内样式2. inner style 内部样式3. outer style 外部样式4. 小结 3 CSS选择器1. 通用选择器…...

Linux_理解程序地址空间和页表

目录 1、进程地址空间示意图 2、验证进程地址空间的结构 3、验证进程地址空间是虚拟地址 4、页表-虚拟地址与物理地址 5、什么是进程地址空间 6、进程地址空间和页表的存在意义 6.1 原因一&#xff08;效率性&#xff09; 6.2 原因二&#xff08;安全性&#xff09; …...

NAND闪存市场彻底复苏

在全球内存市场逐渐走出阴霾、迎来复苏曙光之际&#xff0c;日本存储巨头铠侠&#xff08;Kioxia&#xff09;凭借敏锐的市场洞察力和及时的战略调整&#xff0c;成功实现了从生产紧缩到全面复苏的华丽转身。这一转变不仅彰显了企业在逆境中的生存智慧&#xff0c;也为全球半导…...

过拟合与正则化

Location Beijing 过拟合 对于一个模型 A A A&#xff0c;解向量空间为 θ \theta θ&#xff0c;误差函数用式1表示 J ( θ ) J a c c [ y θ ( x ) − y ] 2 (1) J(\theta)J_{acc}[y_\theta(x)-y]^2\tag{1} J(θ)Jacc​[yθ​(x)−y]2(1) 首先我们考虑用模型 A A A拟合下…...

VMware挂载NAS存储异常处理

问题概述 由于非法关机或恢复&#xff0c;NFS存储可能会出现以下问题&#xff1a; 数据存储处于挂起状态或无法正常识别。虚拟机的配置文件或虚拟磁盘仍然注册在异常数据存储上。系统误认为有虚拟机在使用该数据存储。 问题对策 下面是详细的排查步骤和解决对策&#xff1a…...

Redis 7.x 系列【4】命令手册

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Redis 版本 7.2.5 源码地址&#xff1a;https://gitee.com/pearl-organization/study-redis-demo 文章目录 1. 说明2. 命令手册2.1 Generic2.2 数据类型2.2.1 String2.2.2 Hash2.2.3 List2.2.4 S…...

走进Elasticsearch

什么是ES 是一个分布式、RESTful风格的搜索和数据分析引擎 中文参考文档&#xff1a; 《Elasticsearch中文文档》 | Elasticsearch 技术论坛 elasticSearch官网&#xff1a; Functions and Operators | Elasticsearch Guide [7.11] | Elastic查询方式 Kibana查询&#xff08;原…...

QT TCP服务器和客户端示例程序

下面是一个简单的 Qt TCP 服务器和客户端示例&#xff0c;演示了如何使用 vSetDriver、vSetListener 和 vTcpServerStart 函数。假设 vSetDriver 和 vSetListener 是你定义的自定义函数。 TCP 服务器部分 tcpserver.h #ifndef TCPSERVER_H #define TCPSERVER_H#include <QT…...

Xlua三方库Android编译出错解决办法

Xlua三方库Android编译出错解决办法 最近听老师的热更教程&#xff0c;讲到xlua编译android平台会报错&#xff0c;也是看了老师的博客&#xff0c;按照方法去解决&#xff0c;然而问题并没有解决。应该是因为代码更新或者版本不一样&#xff0c;在此简单记录一下解决过程。 参…...

美国犹他州立大学《Nature Geoscience》(IF=18)!揭示草本植物对土壤有机碳的重要贡献!

随着全球变暖的影响越来越显著&#xff0c;碳固定成为了一个备受关注的话题。在这个背景下&#xff0c;热带草原被认为是一个潜在的碳固定区域。然而&#xff0c;目前的研究主要关注于在热带草原中种植树木&#xff0c;以期望增加土壤有机碳含量。但是&#xff0c;热带草原中的…...

高考专业抉择计算机专业热度不减,兴趣、实力与挑战并存。

作为一名即将步入大学校门的高考生&#xff0c;我对于计算机相关专业是否仍是热门选择感到困惑。在过去几年里&#xff0c;计算机科学与技术、人工智能、网络安全、软件工程等专业一直备受追捧&#xff0c;吸引了无数学生。然而&#xff0c;随着市场竞争加剧和市场饱和度提高&a…...

Flask-RQ

Flask-RQ库教程 Flask-RQ 是一个用于在 Flask 应用中集成 RQ&#xff08;Redis Queue&#xff09;的扩展。RQ 是一个简单的 Python 库&#xff0c;用于将任务排入 Redis 队列并异步执行这些任务。这对于处理长时间运行的任务&#xff08;如发送电子邮件、生成报告等&#xff0…...

LeetCode 58. 最后一个单词的长度

LeetCode 58. 最后一个单词的长度 你一个字符串 s&#xff0c;由若干单词组成&#xff0c;单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串 示例 1&#xff1a; 输入&#xff1a;s “Hello World”…...

3阶段提交协议(3pc)

3阶段提交协议&#xff08;3pc&#xff09; 1 简介 三阶段提交协议是一个强一致、中心化的原子提交协议。解决了分布式事务、副本容错等分布式问题。其核心思想是将2PC的二阶段提交协议的“准备阶段”一分为二&#xff0c;形成了由CanCommit、PreCommit、DoCommit三个阶段组成…...

802.11中的各种帧

在无线网络中&#xff0c;802.11协议定义了三种类型的帧&#xff1a;管理帧&#xff08;Management Frames&#xff09;、控制帧&#xff08;Control Frames&#xff09;和数据帧&#xff08;Data Frames&#xff09;。每种类型的帧都有其特定的功能&#xff0c;帮助维护和管理…...

SAP PP学习笔记21 - 计划策略的Customize:策略组 > 策略 > 需求类型 > 需求类(消费区分,计划区分)

上面几章讲了MTS&#xff0c;MTO&#xff0c;ATO的计划策略。 本章来讲一下它的后台 Customize。 1&#xff0c;Customizeing&#xff1a;Planned Indep.Reqmts Management 这是配置计划策略的整个过程&#xff1a; - Requirements Type / Class 需求类型 / 需求类 - Plann…...

axure9设置组件自适应浏览器大小

问题&#xff1a;预览时不展示下方的滚动条 方法一&#xff1a;转化为动态面板 1.在页面上创建一个矩形 2.右键-转化为动态面板 3.双击进入动态面板设置 4.设置动态面板矩形的颜色 5.删除原来的矩形 6.关闭动态面板&#xff0c;点击预览 7.此时可以发现底部没有滚动条了 方法…...

示例:WPF中TreeView自定义TreeNode泛型绑定对象来实现级联勾选

一、目的&#xff1a;在绑定TreeView的功能中经常会遇到需要在树节点前增加勾选CheckBox框&#xff0c;勾选本节点的同时也要同步显示父节点和子节点状态 二、实现 三、环境 VS2022 四、示例 定义如下节点类 public partial class TreeNodeBase<T> : SelectBindable<…...

C++ explicit关键字的用法

在C中&#xff0c;explicit关键字用于构造函数和转换运算符&#xff0c;以防止隐式转换。它可以帮助我们避免意外的类型转换&#xff0c;从而提高代码的安全性和可读性。explicit关键字只能用于单参数构造函数和转换运算符。 使用explicit的场景 单参数构造函数&#xff1a; 当…...

51.Python-web框架-Django开始第一个应用的增删改查

目录 1.概述 2.创建应用 创建app01 在settings.py里引用app01 3.定义模型 在app01\models.py里创建模型 数据库迁移 4.创建视图 引用头 部门列表视图 部门添加视图 部门编辑视图 部门删除视图 5.创建Template 在app01下创建目录templates 部门列表模板depart.ht…...

Redis之线程IO模型

引言 Redis是个单线程程序&#xff01;这点必须铭记。除了Redis之外&#xff0c;Node.js也是单线程&#xff0c;Nginx也是单线程&#xff0c;但是他们都是服务器高性能的典范。 Redis单线程为什么能够这么快&#xff01; 因为他所有的数据都在内存中&#xff0c;所有的运算都…...

针对微电网中可时移,柔性,基础负荷的电价响应模型---代码解析

前言&#xff1a; 在上两篇帖子中&#xff0c;讲解了我对于粒子群算法的理解&#xff0c;站在巨人的肩膀上去回望&#xff1a;科研前辈们确实非常牛逼&#xff0c;所以它才成为了非常经典的算法。这篇帖子主要是想分享一下&#xff0c;对于微电网、电力系统的论文中&#xff0c…...

git使用http协议时免密pull和push方法

1、创建文件 在项目目录下创建.git-credentials文件&#xff0c;内容如下&#xff0c;填入自己的用户名和密码即可&#xff0c;如果是gitlab&#xff0c;把地址换成自己的gitlab的地址即可。 https://{用户名}:{密码}github.com2、终端执行 git config --global credential.…...

编译期间生成代码(Lombok原理)

通过在编译期间&#xff0c;修改Java的AST(Abstract Syntax Tree)树&#xff0c;可以往类中&#xff0c;添加/修改&#xff08;覆盖&#xff09;方法、属性等。 现在比较常见的三方依赖例子有&#xff1a;Lobbok的Data可以生成get、set方法&#xff0c;Sl4j2可以生成静态常量l…...

第2讲:pixi.js 绘制HelloWorld

基于第0讲和第1讲&#xff0c;我们增添了vite.config.ts文件。并配置了其他的http端口。 此时&#xff0c;我们删除掉没用的东西。 删除 conter.ts、typescript.svg 在main.ts中改成如下内容&#xff1a; import {Application, Text} from pixi.js import ./style.css// 指明…...

golang HTTP2 https测试POST变GET问题小记

概述 因为工作需要协助修改某个golang程序&#xff0c;添加双向认证。但是在调整的过程遇到一个HTTP POST请求变成GET诡异的问题&#xff0c;最后各种搜索&#xff0c;总算解决&#xff0c;博文记录&#xff0c;用于备忘。 代码 服务端 因工作内容&#xff0c;代码有删减&a…...

石家庄做外贸的网站建设/网推是什么

最近项目中涉及很多文件上传的地方&#xff0c;然后文件上传又有很多限制。比如文件大小限制&#xff0c;文件个数限制&#xff0c;文件类型限制&#xff0c;文件上传后的列表样式自定义&#xff0c;包括上传进度条等问题。下面是我对element-ui的上传组件的一些改造&#xff0…...

网站建设的空间是什么意思/广告商对接平台

Elasticsearch 是一个非常强大的搜索引擎。它目前被广泛地使用于各个IT公司。Elasticsearch 是由 Elastic 公司创建并开源维护的。它的开源代码位于 https://github.com/elastic/elasticsearch。同时&#xff0c;Elastic 公司也拥有 Logstash 及 Kibana 开源项目。这个三个开源…...

成都手机网站建/免费下载百度

Matlab 中经常需要对矩阵进行维度上的操作&#xff0c;下面做一个简单的总结&#xff1a; 在Matlab中&#xff0c;不管矩阵的维度是多少&#xff0c;数据在内存中的存储都是按照 “行-列-页” 的顺序进行存储的。比如&#xff1a; >> a [11,12,13; 21,22,23]a <spa…...

锚文本对网站/教育培训机构网站

css: 层叠样式表 作用: 渲染页面 提供工作效率,将html和样式分离 和html的整合 方式1:内联样式表 通过标签的style属性 <xxx style"..."/> 方式2:内部样式表 通过head的子标签Style子标…...

wordpress 文章页 模板/广州网站快速优化排名

某天使用cmd窗口进入mysql&#xff0c;输入命令如下 C:\Users\xxx>net start mysql发生系统错误 5。 拒绝访问。 C:\Users\xxx>mysql -u root -pEnter password: ****ERROR 2003 (HY000): Cant connect to MySQL server on localhost:3306 (10061) 这个ERROR怎么解决…...

网站开发合同样本/免费涨1000粉丝网站

最近在想自己的文章有些是不是写的太难以理解了呢.........竟然好多人看了还是会直接问我很多问题....... 其实PID哈靠自己想像就能自己写出来自己的代码,也许是网上的讲的太过的高深什么积分微分,搞的晕头转向,本来这么实用的想法为什么偏偏说的那么的琢磨不透......感觉那些人…...