【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题

目录

背包问题简介

问题描述

输入:

输出:

动态规划解法

动态规划状态转移

代码实现

代码解释

动态规划的时间复杂度

例子解析

输出:

总结


作者我蓝桥杯:2023第十四届蓝桥杯国赛C/C++大学B组一等奖,所以请听我讲:

137f98fce1bb4b7cb61fcfeb9a3be4ce.png

蓝桥杯是一项备受推崇的编程比赛,参赛者需要通过高效的算法解决各种具有挑战性的问题。今天,我们将深入探讨蓝桥杯经典算法题目之一——0/1背包问题。通过这个题目,我们不仅可以学习如何高效使用动态规划,还能够更好地掌握如何在实际问题中应用算法思想。

背包问题简介

🍎背包问题的核心思想是:给定一组物品,每个物品有一个重量和一个价值,现在有一个背包,背包的容量有限,问如何选择物品放入背包,使得在不超过背包容量的情况下,物品的总价值最大。🍊

应该也很要理解,就是这么个道理: 

🍏在0/1背包问题中,每个物品只能选择放入背包一次,要么放入背包,要么不放入。🍏

5833cb1b733a41e1a68d558fb932d522.png

9651c1d047be455aa92cb563938066bb.png

问题描述

那我们假设我们有一个背包,他的容量为C,有n个物品。其中每个物品有一个重量wi和一个价值vi。我们需要在这些物品中选择若干个物品放入背包,使得背包中物品的总价值最大,并且物品的总重量不超过背包的容量。就是这个问题。

输入:

  • 第1行:nC,表示物品的数量和背包的容量。
  • 第2至n+1行:每行包含两个整数wivi,分别表示第i个物品的重量和价值。

输出:

  • 输出一个整数,表示在不超过背包容量的前提下,能够获得的最大价值。

动态规划解法

是一种通过将复杂问题分解成子问题来求解的方法。在背包问题中,我们可以定义一个二维数组dp[i][j],表示前i个物品中能够在容量为j的背包中获得的最大价值。

8b7a83727f8c4c599f1630d3d02ae359.jpg

 

动态规划状态转移

  • 如果第i个物品不放入背包,那么dp[i][j] = dp[i-1][j],即最大价值与不放入这个物品时的最大价值相同。🥞🥞🥞🥞
  • 如果第i个物品放入背包,那么dp[i][j] = dp[i-1][j-wi] + vi,即最大价值为放入该物品后,剩余容量所能获得的最大价值。🍔🍔🍔🍔🍔

最终,我们要求解的是dp[n][C],即在n个物品和背包容量C下,能够获得的最大价值。

代码实现

import java.util.Scanner;public class Knapsack {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入物品数量和背包容量int n = sc.nextInt();int C = sc.nextInt();// 定义物品的重量和价值int[] weight = new int[n + 1];int[] value = new int[n + 1];// 输入每个物品的重量和价值for (int i = 1; i <= n; i++) {weight[i] = sc.nextInt();value[i] = sc.nextInt();}// dp数组,dp[i][j]表示前i个物品,背包容量为j时的最大价值int[][] dp = new int[n + 1][C + 1];// 动态规划求解for (int i = 1; i <= n; i++) {for (int j = 0; j <= C; j++) {if (j >= weight[i]) {// 如果当前物品可以放入背包,则选择放与不放的最大值dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);} else {// 当前物品不能放入背包时,最大价值与不放当前物品时相同dp[i][j] = dp[i - 1][j];}}}// 输出最大价值System.out.println(dp[n][C]);sc.close();}
}

代码解释

  1. 输入处理:首先通过Scanner读取物品数量n和背包容量C,然后通过循环输入每个物品的重量和价值。
  2. DP数组:使用一个二维数组dp[i][j]表示在前i个物品和容量为j的背包中能获得的最大价值。
  3. 状态转移:遍历每个物品,对于每种可能的背包容量j,根据是否将当前物品放入背包,更新dp[i][j]
  4. 输出:最后输出dp[n][C],即在所有物品和背包容量下能够获得的最大价值。

都挺难的,大家好好消化吧,到时候更新更加详细的教程,方便大家理解。 

动态规划的时间复杂度

该算法的时间复杂度是O(n * C),其中n是物品的数量,C是背包的容量。空间复杂度也是O(n * C),主要由dp数组占据。

例子解析

假设有如下输入:

4 5 2 3 3 4 4 5 5 6

这意味着有4个物品,背包容量为5,物品的重量和价值分别为:

物品重量价值
123
234
345
456

使用动态规划的算法,我们可以求得最大价值为7,即选择物品1(重量2,价值3)和物品2(重量3,价值4)放入背包中,背包容量为5,总价值为7。

输出:

7

9207d6c716b44b068c7f29629358cea6.png

96cee649400f487badc631bd95190ab8.png

 

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

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

相关文章

【C++】抽象之神:类和对象(中)万字详解

Hi&#xff0c;朋友们&#xff0c;好久不见 我们上次学到了C类和对象&#xff08;上&#xff09;&#xff0c;感觉那难度还行&#xff0c;能接受&#xff0c;但这次的类和对象&#xff08;中&#xff09;&#xff0c;一开始真是让我觉得脑子转不动的无力感&#xff0c;难呐&am…

C++手动实现一个HashMap

1.HashMap原理 参考我的博客&#xff1a;https://blog.csdn.net/Revendell/article/details/110009858 开链法&#xff1a;STL的hashtable便是采用开链法解决冲突。这种做法是在每一个表格元素中维护一个list&#xff1a;散列函数为我们分配某一个list&#xff0c;然后我们在…

【Linux】深入理解进程信号机制:信号的产生、捕获与阻塞

&#x1f3ac; 个人主页&#xff1a;谁在夜里看海. &#x1f4d6; 个人专栏&#xff1a;《C系列》《Linux系列》《算法系列》 ⛰️ 时间不语&#xff0c;却回答了所有问题 目录 &#x1f4da;前言 &#x1f4da;一、信号的本质 &#x1f4d6;1.异步通信 &#x1f4d6;2.信…

sql server 数据库还原,和数据检查

右键数据库选择还原&#xff0c; 还原的备份文件必须选择在本地的文件&#xff08;远程文件没有试过&#xff09;还原数据库名字可以修改&#xff0c;然后file选择中有个2个目录data file 的目录 &#xff0c;和log data 的目录都可以重新选择还原到的新的目录&#xff0c;不要…

v31蓝牙信标方案

革新点 带蜂鸣器功能 容易安装和移动 多彩均匀明显的指示灯 长电池寿命&#xff0c;常规使用1-2年 自带1个按键 钮扣电池组供电 产品概述 电子标签拣货系统是一组安装在货架储位上的电子设备&#xff0c;通过计算机与软件的控制&#xff0c;藉由指示灯或数字显示作为辅助…

内存中优雅的csv对象(Python)

磁盘*.csv文件是文本&#xff0c;以行结构的二维list是内存中的“csv”。 (笔记模板由python脚本于2024年12月18日 10:15:23创建&#xff0c;本篇笔记适合学习过list、panda的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&…

OpenGL —— 2.6.1、绘制一个正方体并贴图渲染颜色(附源码,glfw+glad)

源码效果 C++源码 纹理图片 需下载stb_image.h这个解码图片的库,该库只有一个头文件。 具体代码: vertexShader.glsl #version

H5 中 van-popup 的使用以及题目的切换

H5 中 van-popup 的使用以及题目的切换 在移动端开发中&#xff0c;弹窗组件是一个常见的需求。vant 是一个轻量、可靠的移动端 Vue 组件库&#xff0c;其中的 van-popup 组件可以方便地实现弹窗效果。本文将介绍如何使用 van-popup 实现题目详情的弹窗展示&#xff0c;并实现…

Metaploit-永恒之蓝漏洞利用

1&#xff1a;Metaploit介绍   本次测试主要是利用永恒之蓝漏洞对windows7进行控制利用&#xff0c;掌握Metaploit工具的使用&#xff0c;知道永恒之蓝的漏洞利用原理。永恒之蓝是在Windows的SMB服务处理SMB v1请求时发生的漏洞&#xff0c;这个漏洞导致攻击者在目标系统上可…

FPGA高速下载器SZ901

SZ901基于AMD(Xilinx) Virtual Cable协议. 本设备使用千兆网络接口。基于此接口,本设备可以同时支持多达四路FPGA板卡同时调试,每组相互独立,互不干扰。 特点 1,支持JTAG 速度最高53Mb/s&#xff0c;电压范围1.2-3.3V,最高支持200cm排线 2,支持4路JTAG独立使用 3,支持多路…

【递归,搜索与回溯算法】穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝算法入门专题详解

前言 什么是回溯算法&#xff1f; 回溯算法是一种经典的递归算法&#xff0c;通常用于解决组合问题、排列问题和搜索问题等。 回溯算法的基本思想 从一个初始状态开始&#xff0c;按照一定的规则向前搜索&#xff0c;当搜索到某个状态无法前进时&#xff0c;回退…

设计模式之桥接模式:抽象与实现之间的分离艺术

~犬&#x1f4f0;余~ “我欲贱而贵&#xff0c;愚而智&#xff0c;贫而富&#xff0c;可乎&#xff1f; 曰&#xff1a;其唯学乎” 桥接模式概述与角色组成 想象一下你家里的电视遥控器&#xff0c;无论是索尼还是三星的电视机&#xff0c;遥控器的按键功能都差不多&#xff1…

ASRPRO学习笔记一之语音模型位置和语音替换

一、语音替换的步骤 1、扬声器录音 打开GoldWave,点击工具栏中的蓝色控制属性按钮&#xff0c;点击设备&#xff0c;选择扬声器&#xff0c;点击ok。打开电脑上的网易云音乐&#xff0c;点击红色的录制按钮&#xff0c;开始录制音乐&#xff0c;在网易云音乐上点击播放音乐,录…

多因子认证 (Multi-factor authentication, MFA)

多因子认证 (MFA) 是一种思想&#xff0c;而UsernamePassword&#xff0c;OTP等是具体的认证手段。多因子认证就是将这些认证手段结合。 目录 什么是MFAMFA的作用MFA的实际应用 认证认证 (Authentication, AuthN) 因素常见的认证 (Authentication, AuthN) 类型密码认证无密码认…

内存压缩禁用设置

设置禁用内存压缩功能 1、“Win”“X”键→“A”键 2、如果输入“Get-MMAgent”并按“Enter”键&#xff0c;则可以从“MemoryCompression”中检查内存压缩功能的状态。 True启用&#xff0c;False禁用 3、要禁用内存压缩功能&#xff0c;请输入“Disable-MMAgent -mc”并…

素数回文数的个数

素数回文数的个数 C语言代码C 代码Java代码Python代码 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 求11到n之间&#xff08;包括n&#xff09;&#xff0c;既是素数又是回文数的整数有多少个。 输入 一个大于11小于1000的整数n。 输出…

QT网络(一):主机信息查询

网络简介 在QT中进行网络通信可以使用QT提供的Qt Network模块&#xff0c;该模块提供了用于编写TCP/IP网络应用程序的各种类&#xff0c;如用于TCP通信的QTcpSocket和 QTcpServer&#xff0c;用于 UDP 通信的 QUdpSocket&#xff0c;还有用于网络承载管理的类&#xff0c;以及…

Flutter Navigator2.0的原理和Web端实践

01 背景与动机 在Navigator 2.0推出之前&#xff0c;Flutter主要通过Navigator 1.0和其提供的 API&#xff08;如push(), pop(), pushNamed()等&#xff09;来管理页面路由。然而&#xff0c;Navigator 1.0存在一些局限性&#xff0c;如难以实现复杂的页面操作&#xff08;如移…

如何在谷歌浏览器中开启安全浏览

在数字化时代&#xff0c;网络安全变得愈发重要。作为全球最受欢迎的网络浏览器之一&#xff0c;谷歌浏览器提供了多种功能来保护用户的在线安全。本文将详细介绍如何在谷歌浏览器中开启安全浏览&#xff0c;并额外提供一些有用的页面滚动设置、地址栏快捷搜索和跟踪防护的相关…

【物联网技术与应用】实验3:七彩LED灯闪烁

实验3 七彩LED灯闪烁 【实验介绍】 七彩LED灯上电后&#xff0c;7色动闪光LED模块可自动闪烁内置颜色。它可以用来制作相当吸引人的灯光效果。 【实验组件】 ● Arduino Uno主板* 1 ● USB数据线* 1 ● 7彩LED模块*1 ● 面包板*1 ● 9V方型电池*1 ● 跳线若干 【实验原…