背包问题
阅读小提示：这篇文章稍微有点长，希望可以对背包问题进行系统详细的讲解，在看的过程中如果有任何疑问请在评论区里指出。因为篇幅过长也可以进行选择性阅读，读取自己想要的那一部分即可。
前言
背包问题可以看作动态规划系列入门的一个开端，欢迎开启动态规划之旅，在正式学习之前，我想说的是，动态规划真的不难，与贪心算法比较，动态规划有自己的多种板子，也有自己的多种套路；与高级数据结构比较，动态规划的代码量真的非常友好；与字符串类算法比较，动态规划没有那么抽象，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[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
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 = 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
// System.out.print(dp[i] + " ");
// }
System.out.println(dp[k]);
}
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
大数定律 大数定律：是一种描述当试验次数很大时所呈现的概率性致的定律，由概率统计定义“频率收敛于概率”引申服务器托管网而来。换而言之，就是n个独立分布的随机变量其观察值的均值依概率收敛于这些随机变量所属分布的理论均值，也就是总体均值。 例如：假设每次从1、2、…
