开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划（背包+线性DP）--慢慢更新 -> 正文阅读

[数据结构与算法]动态规划（背包+线性DP）--慢慢更新

背包问题

01背包

01背包问题的模型：有规定的空间和若干物体，每个物体给出体积和权重，每个物体最多取一次，要求在规定空间大小内取得权重和最大或者最小

讲一下代码中那个双重循环：

for (int i = 1; i <= N; i++)
		for (int j = 0; j <= V; j++) {
			f[i][j] = f[i - 1][j];
 			if (j >= v[i]) f[i][j] = max(f[i-1][j - v[i]] + w[i], f[i][j]);
		}

f[i][j]表示前i个物品，在当前背包空余容量 j 情况下的最优解（本题表示最大价值）

当前的状态是从之前的状态变化来的，从f[ 0 ][ 0 ]=0开始，有N件物品，需要N次决策，每次决策都决定第i件物品是否放入背包，如果不放入背包，f[ i ][ j ]=f[ i-1 ][ j ]，背包剩余容量仍然是j，所以直接将判断完前i-1个物品所得到的最优解赋给判断完前i件物品的最优解，如果要放入背包，先判断第i件物品的体积是否小于等于剩余容量，如果满足,因为即使体积满足，放入背包后的价值是否变大还要判断，所以f[ i ][ j ]=max(f[ i ][ j ],f[ i-1 ][ j-v[i] ]+w[ i ])(状态转移方程)，在剩余容量为j-v[i]的背包的最优解基础上加上w[i]就是剩余容量为j的最优解

理清楚整个工作过程中背包的变化还是有点绕的，自己代码调试一下可能就明白了

题目链接–01背包问题

朴素版

#include<iostream>
using namespace std;
const int M = 1005;
int v[M], w[M];
int f[M][M];
int main()
{
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= N; i++)
		for (int j = 0; j <= V; j++) {
			f[i][j] = f[i - 1][j];
 			if (j >= v[i]) 
 			    f[i][j] = max(f[i-1][j - v[i]] + w[i], f[i][j]);
		}
	cout << f[N][V];//这个表示判断完N个物体，一开始剩余背包容量为V的最大价值、
	return 0;
}

优化版

分析写在代码内了

for (int i = 1; i <= N; i++)
for (int j = V; j >= v[i]; j--) {
		//for (int j = v[i]; j <= V; j++) {
			//f[i][j] = f[i - 1][j];
			//这一块，因为i是由i-1的状态变化来的，i-2，i-3等等再往前的状态都不用
			//管，只用看前一步，所以变成f[j] = f[j]，这个就可以直接去掉了
 			//if (j >= v[i]) 这个判断也可以直接去掉，把j开始改成v[i]就能保证j>=v[i]恒成立
 			// f[i][j] = max(f[i-1][j - v[i]] + w[i], f[i][j]);
 			f[j] = max(f[j - v[i]] + w[i], f[j]);
 			//当循环是for (int j = v[i]; j <= V; j++)，这样是不对的，因为j前-v[i]<=j后-v[i],小值在在大值前面更新，
 			//那么此时f[j-v[i]]的结果是属于i层，那就相当于 f[i][j] = max(f[i][j - v[i]] + w[i], f[i][j]);
 			//但是按照之前的式子f[j]是在i-1层的基础上跟新的，所以我们将循环的顺序倒一下，
 			//j从V开始计算一直到v[i]，这样大值在小值前面更新，大值在小值基础上更新，此时的小值是i-1层的结果
		}

#include<iostream>
using namespace std;
const int M = 1005;
int v[M], w[M], f[M];
int main()
{
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> w[i];
	
	for (int i = 1; i <= N; i++)
		for (int j = V; j >= v[i]; j--)
			f[j] = max(f[j],f[j - v[i]] + w[i]);

	cout << f[V];

	return 0;
}

完全背包

模型基本与01背包相同，不同的是对于每一件物体可以无穷取
思路也和01背包差不多，思考方式是一样的，不同点在于实行操作后的状态划分更多，01背包只有拿一件或者不拿，完全背包则是可以拿0件，1件，2件…k件
所以朴素写法就加一个循环，用来实现对i种物品拿k件后的状态。

在这里插入图片描述
从y总的课上面截下来的嘻嘻

题目链接–完全背包问题
朴素写法

#include<iostream>
const int M = 1005;
int v[M], w[M], f[M][M];
using namespace std;
int main()
{
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> w[i];

	for(int i=1;i<=N;i++)
		for(int j=1;j<=V;j++)
			for (int k = 0; k * v[i] <= j; k++) {
				//f[i][j] = f[i - 1][j];这一步不需要是因为k从0开始，f[i][j] = f[i - 1][j]就是k=0
				f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
			}
	cout << f[N][V];
	return 0;
}

对这一块进行优化，首先想想看k这一段的循环可不可以去掉
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-2v]+2*w , …)

由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])

for(int i=1;i<=N;i++)
		for(int j=1;j<=V;j++)
			for (int k = 0; k * v[i] <= j; k++) {
				//f[i][j] = f[i - 1][j];这一步不需要是因为k从0开始，f[i][j] = f[i - 1][j]就是k=0
				f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
			}

进行第一步优化，上面那种写法过不了，超时，这种简单优化就可以了

	for(int i=1;i<=N;i++)
		for (int j = 1; j <= V; j++) {
			f[i][j] = f[i - 1][j];//这个别忘了！！
			if(v[i]<=j) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		}

简单优化后和01背包非常像，尤其是这两句：
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

联想到01背包二维到一维的优化，再进一步优化，变成一维数组
就变成这样了酱

#include<iostream>
const int M = 1005;
int v[M], w[M], f[M];
using namespace std;
int main()
{
	int N, V;
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> w[i];

	for (int i = 1; i <= N; i++)
		for (int j = v[i]; j <= V; j++) {
		//这里和 01背包不一样，01是从V->v[i]
		//本质是不一样的，01背包朴素版f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])，
		//f[j] = f[j - v[i]] + w[i]这里要求分f[j - v[i]] + w[i]是要i-1层的结果，第i层是在i-1层基础上更新的
		//完全背包朴素版f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i])，f[j] = f[j - v[i]] + w[i]表示的是k的改变不要求从i-1层变化
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
			
	cout << f[V];
	return 0;
}

01背包和完全背包写法有点像，注意区分

多重背包

与完全背包很像，不同在于没件物品拿取得个数是有限个

朴素版

#include<iostream>
using namespace std;
const int M = 105;
int v[M], w[M], s[M], f[M][M];
int N, V;
int main()
{
	cin >> N >> V;
	for (int i = 1; i <= N; i++)
		cin >> v[i] >> w[i] >> s[i];

	for (int i = 1; i <= N; i++)
		for (int j = 0; j <= V; j++)
			for (int k = 0; k <= s[i] && v[i] * k <= j; k++)
				f[i][j] = max(f[i][j], f[i-1][j - k * v[i]] + k * w[i]);
	cout << f[N][V];
	return 0;
}

优化版
简单说一下优化的思路–二进制优化
题目给出第i种物品最多有s件，那么试试能不能将s件划分成k部分，能够通过这k组物品合成0–s件物品。
举个例子：
s=1023,物品可以取1，2，3…1023件，
将若干个物品打包，1，2，4，8，…,512
前一组数组可以凑出0–1，前两组数据可以凑出0–3，前三组可以凑出0–7…可以凑出0–1023，打包以后的物品就可以看出01背包问题，因为每个组件只能选一次。

本来要枚举1024次，现在只要枚举十次，达到了节省大量时间的目的！！
O(N)->O(logN)

再举个例子：
s=200
分组：1，2，4，8，16，32，64，~~128~~ （128不能要，否则前八组和大于200，前七组和为127，所以再补上一个73）
分组：1，2，4，8，16，32，64，73 这样恰好凑出0–200的任意一个数

给任意一个数s，
我们采用的方式是将其划分成1件，2件，4件，8件…2^k件，c件（c待定是否存在）
始终满足1+2+4+8+2^k=2^k+1-1<=s;如果2^k+1-1<s,再补上c=s-2^k+1+1，显然c<2^k+1

前k组数可以拼成C(k,0)+C(k,1)+C(k,2)+…+C(k,k)=2^k,并且任意拼法都不会重复，因为每个数之间都差2倍，1–2^k能够凑出0–2^k+1-1，补上c后能凑出c–s，那就看一下2^k+1-1–c是否有空隙，因为c<2^k+1，所以无间隔。每个数都能拼出来。
s件拆成log s件，然后再对差分后的物品组进行01背包

朴素做法时间复杂度是NVS->转化后的时间复杂度是NVlogs
题目链接–多重背包问题
这题数据范围较小100100100=1e6,用朴素做法就行
题目链接–多重背包问题II
这题数据范围较大，如果用朴素做法100020002000=41e9，超时，c++1m能处理一亿时间复杂度，优化后10002000log 2000=1000200011大概在21e7，能过。
1000log 2000=100011数组大概开1.1*1e4大小数组就欧克了。

#include<iostream>
using namespace std;
const int M = 25000;
int s[M], v[M], w[M], f[M];
int main()
{
	int N, V;
	cin >> N >> V;

	int pos = 0;
	for (int i = 1; i <= N; i++) {
		int tv, tw, ts, k = 1;
		cin >> tv >> tw >> ts;
		while (ts >= k) {
			pos++;
			v[pos] = k * tv;
			w[pos] = k * tw;
			ts -= k;
			k *= 2;
		}
		if (ts) {
			pos++;
			v[pos] = ts * tv;
			w[pos] = ts * tw;
		}
	}
	N = pos;
	//转化成01背包问题
	for (int i = 1; i <= N; i++)
		for (int j = V; j >= v[i]; j--)
			f[j] = max(f[j], f[j - v[i]] + w[i]);
	cout << f[V];
	return 0;
}

分组背包

分组背包和完全背包类似，完全背包是同一件物品能取多少个，分组背包是一组物品能取哪一个
直接上优化代码了，思路都差不多

关于循环那边其实可以总结一下：
如果当前状态是在上一层状态基础上改变的体积要从大到小枚举，如果不是从上一层状态开始，就从小到大枚举，本篇博客整理的只有01背包和分组背包是从上一层状态改变的。
题目链接–分组背包

#include<iostream>
using namespace std;
const int M = 105;
int s[M], v[M][M], w[M][M], f[M];
int main()
{
	int N, V;
	cin >> N >> V;

	for (int i = 1; i <= N; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i]; j++)
			cin >> v[i][j] >> w[i][j];
	}

	for (int i = 1; i <= N; i++)
		for (int j = V; j >= 0; j--)
			for (int k = 0; k < s[i]; k++)
				if (j >= v[i][k])
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
	cout << f[V];
	return 0;
}

写的时候发现一点问题，所以还是补上朴素版代码

#include<iostream>
using namespace std;
const int M = 105;
int s[M], v[M][M], w[M][M], f[M][M];
int main()
{
	int N, V;
	cin >> N >> V;

	for (int i = 1; i <= N; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i]; j++)
			cin >> v[i][j] >> w[i][j];
	}

	for (int i = 1; i <= N; i++)
		for (int j = 0; j <= V; j++) {
			f[i][j] = f[i - 1][j];//本组任何一件物品都不选
			//这个在k循环前！如果不放在k前放在k循环内部，f[i]本来是在f[i-1]基础上更新的，
			//如果f[i][j]之前已经更新过了，f[i][j]>f[i-1][j],同样j(k不同)，再来一遍f[i][j] = f[i - 1][j];，之前更新过的f[i][j]就作废了，再次比较的是未更新的f[i-1][j];
			for (int k = 0; k < s[i]; k++) {
				if (j >= v[i][k])
					f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
			}
		}
	cout << f[N][V];
	return 0;
}

线性DP

后面展示几个配套的习题

数字三角形

题目链接–数字三角形
又是从y总那边白嫖的分析图，不想自己画了hh

分析：题目求的是从顶点到底部路径上节点之和的最大值，因为只能走左下和右下，所以对当前节点的分析只要看左上方节点和右上方节点就行，因为是上层产生下层，所以下层的最大值就是上层的最大值加上当前节点

构造成一个二维的图像，将各节点存入二维数组进行状态的转移计算

注意的地方是！，因为分析要看左上方节点和右上方节点，对于边界节点例如f[2][1]，可以从f[1][0]或者f[1][1]走到，所以这两个节点都要初始化，总结就是不能只初始化三角形上的节点，还有周围一圈的节点都要初始化。
在这里插入图片描述
代码

#include<iostream>
using namespace std;
const int N = 505, INF = 1e9;
int main()
{
	int a[N][N], f[N][N];
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			cin >> a[i][j];

	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= i + 1; j++)
			f[i][j] = -INF;

	f[1][1] = a[1][1];

	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++)
			f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
	
	int Max = -INF;
	for (int i = 1; i <= n; i++)
		Max = max(Max, f[n][i]);
	cout << Max;

	return 0;
}

最长上升子序列

注意！求得是子序列而不是字串，子序列可以间隔的

题目链接–最长上升子序列
朴素版代码—时间复杂度O(n²)

思想：i作为最长子串终点的位置，通过a[i],a[j]进行比较（j<i),如果a[i]>a[j]，也说以i为结尾的最长子序列可以在以j为结尾的最长子序列上进行修改（前一个小于自己的数结尾的最大上升子序列加上自己，即+1）可能需要更新可能不更新，所以f[i] = max(f[i], f[j] + 1)

注意! i一定是最长上升子串的终点位置，a[i]一定包含在子串内，我一开始没有写这Max = max(Max, f[i])一步，而是直接输出f[n-1]，然后就WA了，芜湖。最长上升子序列不一定有a[n-1]啊，傻了吧…

又是白嫖y总的思维导图
那个椭圆表示f[i]可能来自f[0],f[1]…f[i-1]
在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 1005;
int a[N], f[N];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		f[i] = 1;
	}

	int Max = 1;
	for (int i = 0; i < n; i++)//i作为子序列的终点,找以i为终点的最长子序列
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
			Max = max(Max, f[i]);
		}

	cout << Max;
	return 0;
}