蓝桥杯每日一题------背包问题(一)

时间:2024-02-15 17:45:50

点击可观看配套视频讲解

背包问题

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

前言

背包问题可以看作动态规划系列入门的一个开端,欢迎开启动态规划之旅,在正式学习之前,我想说的是,动态规划真的不难,与贪心算法比较,动态规划有自己的多种板子,也有自己的多种套路;与高级数据结构比较,动态规划的代码量真的非常友好;与字符串类算法比较,动态规划没有那么抽象,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) On3。我们来回顾一下,我们之前有没有类似的代码。在将01背包压缩成1维时,我们是不是有一种错误写法,第二维如果正序遍历会导致同一个物品被多次选择,这对于01背包来说是不合题意的,但是正好符合完全背包的要求,所以之前那个错误的代码完全可以用到完全背包上,并且这个的时间复杂度只需要 O ( n 2 ) O(n^2) On2,代码如下。

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]);
	}
}