蓝桥杯每日一题------背包问题（一）

背包问题

阅读小提示：这篇文章稍微有点长，希望可以对背包问题进行系统详细的讲解，在看的过程中如果有任何疑问请在评论区里指出。因为篇幅过长也可以进行选择性阅读，读取自己想要的那一部分即可。

前言

背包问题可以看作动态规划系列入门的一个开端，欢迎开启动态规划之旅，在正式学习之前，我想说的是，动态规划真的不难，与贪心算法比较，动态规划有自己的多种板子，也有自己的多种套路；与高级数据结构比较，动态规划的代码量真的非常友好；与字符串类算法比较，动态规划没有那么抽象，ok话不多说，开始吧。
首先介绍一下动态规划的步骤（我自己总结的，自己用起来感觉还不错，y总也有介绍过闫式dp分析法，大家感兴趣可以看一看，怎么方便怎么来）
求解动态规划有两个大的阶段，分别是定义dp数组和推导状态转移方程。大家觉得这两个哪个重要呢？诚然状态转移方程是动态规划的关键，但是我在做题的过程中感受到当你的dp数组定义正确了，状态转移方程的推导就是自然而然的事情，所以对我来说，最关键的是定义dp数组。我们可以按照下面的步骤定义dp数组。
第一步：缩小规模。大家在大学学到动态规划时，一般都会拿来和贪心比，和分治比，无论哪一个我们都不能一口吃个胖子，都是从最基础的那个地方开始，一步一步往下走，最终走到终点。既然要缩小规模，那必然要有一个维度来定义当前的规模，放在背包问题里，规模就是考虑的物品的个数，那么用一个维度就可以了，放在区间dp里，规模是区间的大小，而不同的区间结果是不一样的，所以需要两个维度来表示区间的左右端点。
第二步：限制。放在背包问题里，限制就是背包的容量，你选的物品的总体积不能超过当前背包容量，所以你需要一个维度来表示当前的体积。
第三步：写出dp数组。走到这里，根据规模和限制定义了dp数组，dp[i][j]表示当前考虑了前i个物品，背包容量为j时能够装的最大价值。我们求的就是最大价值，那么dp数组对应的值就是最大价值，一般和所求是一样的，求什么就记录什么。
第四步：修改dp数组。这一步就是在写状态转移方程时，你发现定义的dp数组维度少了，还需要其它信息，那么这个时候就是需要什么往dp数组里面加什么，即增加维度，但是要注意一点，一般dp数组的维度和时间复杂度是正相关的，维度过多，很有可能超时。

01背包

在这里插入图片描述
定义dp数组
第一步：缩小规模。考虑n个物品，那我就先考虑1个物品，在考虑2个物品…，需要一个维度表示当前考虑的物品个数。
第二步：限制。所选物品个数不能超过物品容量，那么需要一个维度记录当前背包的容量。
第三步：写出dp数组。dp[i][j]表示当前考虑了前i个物品，背包容量为j时的最大价值。
第四步：推状态转移方程。dp[i][j]应该从哪里转移过来呢，必然是从前i-1个物品转移，我要考虑两种情况，对于第i个物品，可以选择要它，也可以不要它，如果要第i个物品，我就需要背包里面给我预留出第i个物品的体积，也就是从a[i-1][j-v[i]]转移，同时也能获得该物品的价值。如果不要第i个物品，那么之前从前一个状态相同容量的背包转移过来就行，即a[i-1][j]。
综上状态转移方程如下
a[i][j] = max(a[i-1][j],a[i-1][j-v[i]]+w[i])
考虑写代码了
第一步：确定好遍历顺序，对于背包问题，一般第一个for遍历规模，第二个for遍历限制。

for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			dp[i][j] = dp[i-1][j];//为什么要在这里转移，因为这个转移是一定会发生的，而另一个转移不一定会发生
			if(j>=v[i])
				dp[i][j] = Math.max(dp[i-1][j-v[i]]+w[i], dp[i][j]);
		}
	}

第二步：考虑是否要对dp数组初始化，这里不需要，因为最开始的状态考虑前0个物体，它的值就是0，不需要管。
全部代码如下，

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int V = scanner.nextInt();
	int[] v = new int[n+1];
	int[] w = new int[n+1];
	for (int i = 1; i < w.length; i++) {
		v[i] = scanner.nextInt();
		w[i] = scanner.nextInt();
	}
	int[][] dp = new int[n+1][V+1];
//	for (int i = 0; i < dp.length; i++) {
//		dp[0][i] = 1;
//	}
	for (int i = 1; i < dp.length; i++) {
		for (int j = 0; j < V+1; j++) {
			dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
			if(v[i]<=j) {
				dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
			}
		}
	}
	System.out.println(dp[n][V]);
}
}

考虑对dp数组进行维度优化，这里的优化并不会降低它的时间复杂度，但是可以减低空间复杂度，提高空间利用率，并且它也可以算是滚动dp的一个因子，而且里面有一个思想在后续做题的过程中也需会用到！
我们考虑一下在转移的过程中我只用了a[i]和a[i-1]对于a[i-2],a[i-3]我后续都用不到了，所以没有必要存它，考虑如果我只用一个一维的dp，思路还是一样的，但是代码该怎么写。
令dp[i]表示背包容量为i时最多能容纳的物品价值。自己尝试把代码里表示物品个数的那一维删掉，就成了

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	int V = scanner.nextInt();
	int[] v = new int[n+1];
	int[] w = new int[n+1];
	for (int i = 1; i < w.length; i++) {
		v[i] = scanner.nextInt();
		w[i] = scanner.nextInt();
	}
	int[] dp = new int[V+1];
	for (int i = 1; i < dp.length; i++) {
		for (int j = 0; j < V+1; j++) {
			//dp[j] = Math.max(dp[j], dp[j]);
			if(v[i]<=j) {
				dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
			}
		}
	}
	System.out.println(dp[V]);
}
}

直接这样提交可以过吗？当然不可以，我们还记得我们的题目是每个物品只有一个吗？我们分析一下dp[j] = Math.max(dp[j], dp[j-v[i]]+w[i]);
假设当前遍历到了i=5，假设j=5时，dp[j]=dp[j-v[i]]+w[i].说明此时我们拿了第5个物品，当遍历到j=10时假设此时v[i]=5，dp[10]=dp[10-5]+w[i]=dp[5]+w[i]，可以看见dp[10]是从dp[5]转移的，但是我们的本意是不是dp[5]表示的应该是i=4时的结果，但是刚刚我们也看见了，遍历到dp[10]时，dp[5]已经被更新了，它不是i=4时的dp[5]，所以会出错。好，我们再深究一下，出错的结果是啥？dp[5]是不是已经选了物品5了？此时dp[10]==dp[5]+w[i]又选了一次物品5，说明物品5被选了多次，而题目要求每个物品只能选一次，所以不符合题意。如果改一改，改成每个物品可以选无数次，那么这里就是没有问题，记住这一点。
回到这个题目，那我们应该怎么改，在求dp[10]时，会用到dp[5]，归纳一下，在求dp[i]时，会用到dpj，我们在遍历到i之前不能动dp[j]。也就是说，先遍历大的数，所以我们直接倒序遍历就行了。来看代码吧，

	for (int j = 0; j < n; j++) {
			for (int i = k; i >= v[j]; i--) {//i<v[j]时不能转移，所以直接遍历到v[j]就行，这样后面就不用if语句判断是否能转移了。
				dp[i] = Math.max(dp[i], dp[i - v[j]] + w[j]);
			}
		}

全部代码

import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] v = new int[n];
		int[] w = new int[n];
		for (int i = 0; i < n; i++) {
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		int[] dp = new int[k + 1];
		for (int j = 0; j < n; j++) {
			for (int i = k; i >= v[j]; i--) {
				// System.out.println("---");
				dp[i] = Math.max(dp[i], dp[i - v[j]] + w[j]);
			}
		}
		System.out.println(dp[k]);
	}
}

借此机会，再讲一下滚动dp，他不算是单独的一种dp，只是对dp的一种空间优化方法，防止爆内存。刚刚讲过，在dp数组遍历的过程中我只用到了当前为i时的状态和前一个为i-1时的状态，其它的都不要了，所以其实我可以把dp[n+1][V+1]，变成dp[2][V+1]，如果dp[0][V+1]表示考虑了前0个物品的状态，遍历到i=1时，用dp[1][V+1]表示考虑了前1个物品的状态，遍历到i=2时，前0个物品的状态我不需要记录了，此时可以拿dp[0][V+1]表示考虑了前2个物品的状态，如此循环往复。可以发现这是交替使用的，那么数字里面什么是交替出现的？奇偶数呀，所以可以用奇偶数来判断，如dp[i&1][j]和dp[(i-1)&1][j]。在使用滚动dp时，其实修改很好修改，只要在你原来的代码里，注意是使用二维数组的那个代码哈，把dp[i][j]和dp[i-1][j]改成dp[i&1][j]和dp[(i-1)&1][j]就行了。因此它也不易出错，比起刚刚介绍的直接把dp数组减少一维。看代码吧。

import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] v = new int[n + 1];
		int[] w = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		int[][] dp = new int[2][k + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= k; j++) {
				// System.out.println(i + " " + j + " ---------");
				if (j >= v[i]) {
					dp[i&1][j] = Math.max(dp[(i - 1)&1][j], dp[(i - 1)&1][j - v[i]] + w[i]);
				} else {
					// System.out.println(i + " " + j);
					dp[i&1][j] = dp[(i - 1)&1][j];
				}

			}
		}
		System.out.println(dp[n&1][k]);
	}
}

完全背包

在这里插入图片描述
完全背包和01背包的不同在于完全背包对每个物品的可选次数没有限制，那么在遍历的时候就会比原来多出一个维度，dp数组的定义还是一样的，dp[i][j]表示考虑前i个物品当前背包容量为j时的最大价值。那么可选物品不受限制如何体现呢？
01背包在递推dp数组时有两个嵌套for循环，第一层遍历当前考虑前i个物品，第二层遍历当前背包的容量为j，那么我们需要加入一个维度，这个维度表示选择j2个第i个物品，完整代码如下

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
      		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] v = new int[n + 1];
		int[] w = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		int[][] dp = new int[n + 1][k + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < k + 1; j++) {
				for (int j2 = 0; j2 * v[i] <= j; j2++) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - j2 * v[i]] + j2 * w[i]);
				}

			}
		}
		System.out.println(dp[n][k]);
	}
}

此时的复杂度就是 O （ n 3 ） O（n^3） O（n3）。我们来回顾一下，我们之前有没有类似的代码。在将01背包压缩成1维时，我们是不是有一种错误写法，第二维如果正序遍历会导致同一个物品被多次选择，这对于01背包来说是不合题意的，但是正好符合完全背包的要求，所以之前那个错误的代码完全可以用到完全背包上，并且这个的时间复杂度只需要 O （ n 2 ） O（n^2） O（n2），代码如下。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] v = new int[n + 1];
		int[] w = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			v[i] = scanner.nextInt();
			w[i] = scanner.nextInt();
		}
		int[] dp = new int[k + 1];
		for (int i = 1; i <= n; i++) {
//			for (int j = 0; j < dp.length && j >= v[i]; j++) {
			for (int j = v[i]; j < dp.length; j++) {
//				System.out.println(dp[i] + " " + (dp[j - v[i]] + w[i]) + " " + i + " " + j);
				dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
			}
		}
//		for (int i = 0; i < dp.length; i++) {
//			System.out.print(dp[i] + " ");
//		}
		System.out.println(dp[k]);
	}
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

UE4运用C++和框架开发坦克大战教程笔记（十八）（第55~57集）

UE4运用C++和框架开发坦克大战教程笔记（十八）（第55~57集）

UE4运用C和框架开发坦克大战教程笔记&#xff08;十八&#xff09;&#xff08;第55~57集&#xff09; 55. UI 进入退出动画HideOther 面板出现时隐藏其他面板添加面板出现和收起的动画效果编写遮罩管理器前的准备 56. 弹窗进入界面57. UI 显示隐藏与遮罩转移完善遮罩管理器 55…
阅读更多...
ARM汇编[0] hello world

ARM汇编[0] hello world

文章目录 简述寄存器语法系统调用例程 简述 如果不了解x86汇编的话建议先了解下&#xff0c;x86资料多、环境好搞、容易入门 阿尔可是急于求成的人&#xff0c;希望赶快看到成果&#xff1b; 所以本篇文章不会东讲西讲展开讲&#xff0c;只讲让hello world汇编能跑起来的关键…
阅读更多...
2 月 9 日算法练习- 数据结构 - 除夕快乐♪٩(´ω`)و♪

2 月 9 日算法练习- 数据结构 - 除夕快乐♪٩(´ω`)و♪

翻转括号序列 暴力过20%数据 思路&#xff1a;括号合法序列问题可以利用前缀和&#xff0c;将"(“看成 1&#xff0c;”)"看成 0&#xff0c;规律是到某个位置为止的前缀和>0并且到最后前缀和0。 #include<bits/stdc.h> using namespace std; const int N…
阅读更多...
鸿蒙原生应用再添新丁！央视新闻 入局鸿蒙

鸿蒙原生应用再添新丁！央视新闻 入局鸿蒙

鸿蒙原生应用再添新丁&#xff01;央视新闻 入局鸿蒙 来自 HarmonyOS 微博2月9日消息&#xff0c;#央视新闻启动鸿蒙原生应用开发#中央广播电视总台旗舰央视新闻客户端正式宣布&#xff0c;将基于HarmonyOS NEXT鸿蒙星河版&#xff0c;启动央视新闻 鸿蒙原生应用开发&#xf…
阅读更多...
扑克牌大小（模拟）

扑克牌大小（模拟）

题目 import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);String s sc.nextLine();String[] ss s.split("-");StringBuffer s1 new StringBuffer();StringBuffer s2 new StringBuffer(…
阅读更多...
Java基础知识总结（持续更新中）

Java基础知识总结（持续更新中）

Java基础知识&#xff08;持续更新&#xff09; 类型转化&#xff1a;数字、字符串、字符之间相互转化 数字 <-> 字符串 // 数字转字符串 // method1int number 5;String str String.valueOf(number);// method2int number 5;Integer itr number; //int装箱为对…
阅读更多...
vue3 之 通用组件统一注册全局

vue3 之 通用组件统一注册全局

components/index.js // 把components中的所组件都进行全局化注册 // 通过插件的方式 import ImageView from ./ImageView/index.vue import Sku from ./XtxSku/index.vue export const componentPlugin {install (app) {// app.component(组件名字&#xff0c;组件配置对象)…
阅读更多...
moduleID的使用

moduleID的使用

整个平台上有很多相同的功能&#xff0c;但是需要不同的内容。例如各个模块自己的首页上有滚动新闻、有友好链接等等。为了公用这些功能&#xff0c;平台引入了moduleID的解决方案。 在前端的配置文件中&#xff0c;配置了模块号&#xff1a; 前端页面请求滚动新闻时&#xff0…
阅读更多...
一款VMP内存DUMP及IAT修复工具

一款VMP内存DUMP及IAT修复工具

前言 加壳是恶意软件常用的技巧之一&#xff0c;随着黑客组织技术的不断成熟&#xff0c;越来越多的恶意软件家族都开始使用更高级的加壳方式&#xff0c;以逃避各种安全软件的检测&#xff0c;还有些恶意软件在代码中会使用各种多态变形、加密混淆、反调试、反反分析等技巧&a…
阅读更多...
基于JAVA的教学资源共享平台 开源项目

基于JAVA的教学资源共享平台 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课程资源模块2.4 课程作业模块2.5 课程评价模块 三、系统设计3.1 用例设计3.2 类图设计3.3 数据库设计3.3.1 课程档案表3.3.2 课程资源表3.3.3 课程作业表3.3.4 课程评价表 四、系统展…
阅读更多...
单片机学习笔记---DS1302时钟

单片机学习笔记---DS1302时钟

上一节我们讲了DS1302的工作原理&#xff0c;这一节我们开始代码演示。 新创建一个工程写上框架 我们需要LCD1602进行显示&#xff0c;所以我们要将LCD1602调试工具那一节的LCD1602的模块化代码给添加进来 然后我们开始创建一个DS1302.c和DS1302.h 根据原理图&#xff0c;为了…
阅读更多...
005集——shp格式数据转换乱码问题——arcgis

005集——shp格式数据转换乱码问题——arcgis

shp数据格式与其他数据格式转换过程中会遇到乱码等问题&#xff0c;原因如下&#xff1a; 在Shapefile头文件&#xff08;dBase Header&#xff09;中&#xff0c;一般会包含字符编码信息&#xff0c;这个信息称为 LDID &#xff08; Language Driver ID&#xff09;。在使用ar…
阅读更多...
博主：今日无更

博主：今日无更

今天放个假&#xff0c;不更新文章 &#xff08;占位符&#xff09;
阅读更多...
龙芯开启ssh服务——使用Putty连接

龙芯开启ssh服务——使用Putty连接

本文采用龙芯3A6000处理器&#xff0c;Loongnix操作系统。 为了能使用其他电脑远程操控龙芯电脑&#xff0c;需要打开loongnix的ssh服务&#xff0c;并在其他电脑里使用putty连接loongnix。 1 修改ssh配置文件 命令行输入&#xff1a; sudo vim /etc/ssh/sshd_config按下i插…
阅读更多...
防疫物资管理新篇章：Java+SpringBoot实战

防疫物资管理新篇章：Java+SpringBoot实战

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…
阅读更多...
问题：A注册会计师必须在期中实施实质性程序的情形是（）。 #学习方法#其他

问题：A注册会计师必须在期中实施实质性程序的情形是（）。 #学习方法#其他

问题&#xff1a;A注册会计师必须在期中实施实质性程序的情形是&#xff08;&#xff09;。 A&#xff0e;甲公司整体控制环境不佳 B&#xff0e;将期中实质性程序所获证据与期末数据进行比较 C&#xff0e;评估的认定层次重大错报风险很高 D&#xff0e;没有把握通过在期中…
阅读更多...
Sklearn、TensorFlow 与 Keras 机器学习实用指南第三版（七）

Sklearn、TensorFlow 与 Keras 机器学习实用指南第三版（七）

原文&#xff1a;Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第十六章&#xff1a;使用 RNN 和注意力进行自然语言处理 当艾伦图灵在 1950 年想象他著名的Turing 测试时&#xff0c;他提出了…
阅读更多...
leetcode（双指针）283.移动零（C++详细题解）DAY3

leetcode（双指针）283.移动零（C++详细题解）DAY3

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 示例 1: 输入…
阅读更多...
C语言每日一题（52）单值二叉树

C语言每日一题（52）单值二叉树

力扣网 965 单值二叉树 题目描述 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时&#xff0c;才返回 true&#xff1b;否则返回 false。 示例 1&#xff1a; 输入&#xff1a;[1,1,1,1,1,null,1] 输出&#xff1a;t…
阅读更多...
MySQL数据库⑦_复合查询+内外链接（多表/子查询）

MySQL数据库⑦_复合查询+内外链接（多表/子查询）

目录 1. 回顾基本查询 2. 多表查询 2.1 笛卡尔积初步过滤 3. 自连接 4. 子查询 4.1 单行子查询 4.2 多行子查询 4.2 多列子查询 4.2 from子句中使用子查询 5. 合并查询 6. 内外链接 6.1 内连接 6.2 左外链接 6.2 右外连接 本篇完。 1. 回顾基本查询 先回顾一下…
阅读更多...
最新文章

Copyright @ 2022~2023