0-1背包问题-例题

题目摘自《卡码网》46题

题意理解

        m种材料——对应m物品

        大小问n的行李箱——对应大小为n的背包

        所以该问题是一个0-1背包问题,采用动态规划的一般思路来解题。

解题思路

        动规五部曲:

        (1)定义二维dp数组,明确dp[i][j]的定义

                dp[i][j]表示编号在[0,i]的物品任取,放入大小为j的背包内,所得的最大价值

        (2)递推公式:

                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])

        (3)初始化:根据递推公式可以看出,总是由左边和上边推导当前的数值,所以初始化第一行第一列。

        (4)遍历顺序:先物品后背包,先背包后物品都可以,因为二维dp数组保留了两个维度所有值。

        (5)打印结果,debug.

1.二维dp数组解决0-1背包问题

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int m,n=0;m=sc.nextInt();n=sc.nextInt();int[] volumeArr=new int[m];int[] valuesArr=new int[m];for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();Main obj=new Main();System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));}public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){//定义dp数组int dp[][]=new int[volumeArr.length][bagSize+1];for (int i = 0; i <volumeArr.length; i++) {Arrays.fill(dp[i], -1);}//初始化-第一列:背包大小为0for(int i=0;i<valuesArr.length;i++) dp[i][0]=0;//初始化-第一行:能放入则放入for(int j=1;j<=bagSize;j++){if(volumeArr[0]>j){dp[0][j]=0;}else{dp[0][j]=valuesArr[0];}}//遍历:双for循环for(int i=1;i<volumeArr.length;i++){for(int j=1;j<=bagSize;j++){//判断是否能否加入if(volumeArr[i]>j){//不能放入dp[i][j]=dp[i-1][j];}else{//能放入dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-volumeArr[i]]+valuesArr[i]);}}}return dp[volumeArr.length-1][bagSize];}
}

2.一维dp数组(一维动态滚动数组)解决0-1背包问题——存储压缩 

dp[j]表示背包大小为j时,任意取放物品能获得的最大价值。

递推公式:dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i])

注意:前面的值会影响后面值的操作,所以在遍历背包大小时,从后往前操作,防止重复操作同一行数据,导致物品重复加入。

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int m,n=0;m=sc.nextInt();n=sc.nextInt();int[] volumeArr=new int[m];int[] valuesArr=new int[m];for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();Main obj=new Main();System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));}public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){//定义dp数组int dp[]=new int[bagSize+1];//初始化Arrays.fill(dp,0);//遍历:双for循环for(int i=0;i<volumeArr.length;i++){for(int j=bagSize;j>=0;j--){//判断是否能否加入if(volumeArr[i]<=j){//能放入dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i]);}}}return dp[bagSize];}
}

 

3.分析

时间复杂度

        O(m*n)

空间复杂度

        二维:O(m*n)

        一维:O(n)

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

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

相关文章

springBoot-自动配置原理

以下笔记内容&#xff0c; 整理自B站黑马springBoot视频&#xff0c;抖音Holis 1、自动配置原理 1.收集Spring开发者的编程习惯&#xff0c;整理开发过程使用的常用技术列表一>(技术集A) 2.收集常用技术(技术集A)的使用参数&#xff0c;整理开发过程中每个技术的常用设置列表…

Python解析参数的三种方法

今天我们分享的主要目的就是通过在 Python 中使用命令行和配置文件来提高代码的效率 Let’s go! 我们以机器学习当中的调参过程来进行实践&#xff0c;有三种方式可供选择。第一个选项是使用 argparse&#xff0c;它是一个流行的 Python 模块&#xff0c;专门用于命令行解析&…

小家电type-c接口PD诱骗

小家电Type-C接口PD诱骗&#xff1a;未来充电的便捷与安全 随着科技的不断发展&#xff0c;Type-C接口已经成为了许多小家电产品的标配。而PD&#xff08;Power Delivery&#xff09;诱骗技术&#xff0c;作为一种新兴的充电技术&#xff0c;更是为小家电产品的充电带来了前所…

Transformer架构和对照代码详解

1、英文架构图 下面图中展示了Transformer的英文架构&#xff0c;英文架构中的模块名称和具体代码一一对应&#xff0c;方便大家对照代码、理解和使用。 2、编码器 2.1 编码器介绍 从宏观⻆度来看&#xff0c;Transformer的编码器是由多个相同的层叠加⽽ 成的&#xff0c;每个…

FreeRTOS——软件定时器

一、什么是定时器 简单可以理解为闹钟&#xff0c;到达指定一段时间后&#xff0c;就会响铃。 STM32 芯片自带硬件定时器&#xff0c;精度较高&#xff0c;达到定时时间后会触发中断&#xff0c;也可以生成 PWM 、输入捕获、输出 比较&#xff0c;等等&#xff0c;功能强大&a…

P12 音视频复合流——TS流讲解

前言 从本章开始我们将要学习嵌入式音视频的学习了 &#xff0c;使用的瑞芯微的开发板 &#x1f3ac; 个人主页&#xff1a;ChenPi &#x1f43b;推荐专栏1: 《C_ChenPi的博客-CSDN博客》✨✨✨ &#x1f525; 推荐专栏2: 《Linux C应用编程&#xff08;概念类&#xff09;_C…

电脑文件mfc100u.dll丢失的解决方法分析,怎么修复mfc100u.dll靠谱

mfc100u.dll丢失了要怎么办&#xff1f;其实很多人都遇到过这样的电脑故障吧&#xff0c;说这个mfc100u.dll文件已经不见了&#xff0c;然后一些程序打不开了&#xff0c;那么这种情况我们要怎么解决呢&#xff1f;今天我们就来给大家详细的说说mfc100u.dll丢失的解决方法。 一…

李家的张麻子:ETL工程师的数据库编程之旅,用ChatGPT打破常规!

数据库编程大赛&#xff1a;一条SQL计算扑克牌24点 12月27日&#xff0c;NineData和云数据库技术社区主办&#xff0c;华为云、火山引擎、开源中国、云和恩墨、TDengine、云猿生数据、DORIS、ITPUB等协办单位和媒体&#xff0c;共同举办了本次《数据库编程大赛》。大赛题目「用…

EtherCAT主站SOEM -- 13 --Qt-Soem通过界面按键控制 EtherCAT IO模块的io输出

EtherCAT主站SOEM -- 13 --Qt-Soem通过界面按键控制 EtherCAT IO模块的io输出 一 mainwindow.c 文件函数:1.1 自定义PDO配置2.2 主站初始化2.3 去motrorcontrol界面二 motrorcontrol.c 文件三 allvalue.h 文件该文档修改记录:总结一 mainwindow.c 文件函数: mainwindow主界…

20240105移远的4G模块EC20在Ubuntu 20.04.6 LTS下使用联通5G卡上网的步骤

20240105移远的4G模块EC20在Ubuntu 20.04.6 LTS下使用联通5G卡上网的步骤 2024/1/5 10:11 缘起&#xff1a;需要在Firefly的AIO-3399J开发板上调试移远的4G模块EC20&#xff08;Android10/11/12&#xff09;&#xff0c;需要现在先测试EC20的好坏&#xff01; 陶老板告诉我找一…

PPT插件-大珩助手-免费功能-特殊格式介绍

上、下标切换 直接切换选中的字符为上、下标。 大小金额 支持超大金额的大写金额转换 当前日期 本次打开文件的时间 转二维码 将当前选中的文字&#xff0c;转为二维码图片&#xff0c;并插入到PPT当前位置 特殊字符 内置常用的特殊字符&#xff0c;点击使用 软件介绍 …

致命勒索|揭秘2023年度十大勒索团伙

2023年&#xff0c;全球数字化转型加速 &#xff0c;5G网络以及人工智能的高速发展&#xff0c;都给网络安全带来了新的挑战 。受地缘政治因素及疫情影响&#xff0c;国际局势动荡不安&#xff0c;经济衰退&#xff0c; 越来越多的网络攻击组织建立了高效的商业模式&#xff0c…

你们做外贸主要的获客渠道有哪些?

昨天跟一个同行朋友聊天&#xff0c;他原本主打产品是做动力类的&#xff0c;这两年竞争太大&#xff0c;订单也减少了很多。为了求发展&#xff0c;就拓品了&#xff0c;而拓展的新品刚好是我们这一块&#xff0c;而且非常迅速地找到场地把生产线弄了起来&#xff0c;还不断扩…

mysql原理--InnoDB的Buffer Pool

1.缓存的重要性 对于使用 InnoDB 作为存储引擎的表来说&#xff0c;不管是用于存储用户数据的索引&#xff08;包括聚簇索引和二级索引&#xff09;&#xff0c;还是各种系统数据&#xff0c;都是以 页 的形式存放在 表空间 中的&#xff0c;而所谓的 表空间 只不过是 InnoDB 对…

将Django项目从本地上传至宝塔服务器(踩坑记录)

文章目录 写在前面配置本地文件配置宝塔面板解决遇到问题展示运行结果热门文章 自我介绍 ⭐2022年度CSDN 社区之星 Top6 ⭐2023年度CSDN 博客之星 Top16 ⭐2023年度CSDN 城市之星 Top2&#xff08;苏州&#xff09; ⭐CSDN Python领域 优质创作者 ⭐CSDN 内容合伙人 推荐热门…

Dockerfile语法和简单镜像构建

Dockerfile是一个用于定义Docker镜像的文本文件&#xff0c;包含了一系列的指令和参数&#xff0c;用于指示Docker在构建镜像时应该执行哪些操作&#xff0c;例如基于哪个基础镜像、复制哪些文件到镜像中、运行哪些命令等。 Dockerfile文件的内容主要有几个部分组成&#xff0c…

Python - 深夜数据结构与算法之 Two-Ended BFS

目录 一.引言 二.双向 BFS 简介 1.双向遍历示例 2.搜索模版回顾 三.经典算法实战 1.Word-Ladder [127] 2.Min-Gen-Mutation [433] 四.总结 一.引言 DFS、BFS 是常见的初级搜索方式&#xff0c;为了提高搜索效率&#xff0c;衍生了剪枝、双向 BFS 以及 A* 即启发式搜索…

pyqt调用UI和开启子进程

UI制作 qrc 注意调用UI前把样式表里绑定的资源(qrc)转换成py导入进去 xxx.qrc转xxx.py 两种方法 1命令 pyrcc5 -o icons_rc.py icons.qrc 2外部工具pyrcc 实参 -o $FileNameWithoutExtension$.py $FileNameWithoutExtension$.qrcsdz.qrc→→sdaz.py 在代码里写 import…

【模拟IC学习笔记】 采样保持电路的设计

目录 采样保持工作原理 概念 时域响应-采保信号 采样网络的KT/C噪声 采样电容大小的选取 采样抖动(jitter) jitter对SNR的影响 法一 法二 采样开关的种类 单MOS管 实践&#xff1a;Nmos导通电阻 传输门 栅压自举开关 采样技术 上极板采样 下极板采样 采样保持…

数据库的导入导出以及备份

1.数据库的导出和导入 一.navicat导入导出 导入&#xff1a;右键➡运行SQL文件 导出选&#xff1a;中要导出的表➡右键➡转储SQL文件➡数据和结构 mysqldump命 1. 进入navicat安装目录的bin目录&#xff0c;cmd打开命令窗口 2. mysql -u用户名 -p ➡ 输入密码 3. creat…