T1 01背包

题目描述：有 N件物品和一个容量是V的背包。每件物品只能使用一次。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	for(int i=0;i<=m;i++){
		f[0][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(v[i]<=j){
				f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
			}else{
				f[i][j]=f[i-1][j];
			}
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

思路：

不选第i个物品：意味着f[i][j]=f[i-1][j]，此公式的含义是，不选第i个物品，那么从前i-1个物品中选体积不超过j的最大值。

选第i个物品：意味着 f[i][j]=f[i-1][j-v[i]]+w[i]，此公式的含义是，选第i个物品，那么在选好了前i-1个物品的情况下，留出v[i]的空间（即j-v[i]）给i物品，再加上第 个物品的价值w[i]即可。

那么选和不选中选择最大值就是我们f[i][j]的值，统一后公式为：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]。

初始状态：f[1...n][0]=0，即体积为0时，不管选什么物品，最大价值都为0。

T2 完全背包

题目描述：有N种物品和一个容量是V的背包，每种物品都有无限件可用。

第i种物品的体积vi，价值是wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

思路：

此代码在01背包问题的基础上，加了一个物品无限的条件。

但是，此代码时间复杂度为O$(nm^2)$ ，会超时，需要优化。

优化过程如下：

f(i,j)=max(f(i-1,j),f(i-1,j-v)+wi,f(i-1,j-2vi)+2w)

f(i,j-vi)=max(f(i-1,j-vi),f(i-1,j-2vi)+w)

可以发现，第二个式子相当于第一个式子除第一项之外的后面的项，只是少加了一个wi而已。

那么f(i,j)=max(f(i-1,j),f(i,j-vi)+wi)

01背包的状态转移方程是：

f(i,j)=max(f(i-1,j),f(i-1,j-vi)+wi)

可以发现01背包问题是从i-1状态转移而来，而完全背包是从第i层状态转移而来。

可以发现，第二个式子相当于第一个式子除第一项之外的后面的项，只是少加了一个而已

更通俗的理解是，我们在考虑第i个物品时，先假设现在取0个，那么后续的无论取多少个，都是从取0层状态而来，即本层。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k*v[i]<=j;k++){
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);			
			}
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

T3数字三角形

题目描述：

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=550;
int a[N][N],f[N][N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	memset(f,-0x3f,sizeof f);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(i==1&&j==1){
				f[i][j]=a[i][j];
			}else{
				f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
			}
		}
	}
	int ans=-1e9;
	for(int i=1;i<=n;i++){
		ans=max(ans,f[n][i]);
	}
	cout<<ans;
	return 0;
}

思路：

T4最长上升子序列I

题目描述：

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int a[N],f[N],n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	int mx=1;
	for(int i=1;i<=n;i++){
		mx=max(mx,f[i]);
	}
	cout<<mx;
	return 0;
}

思路：

T5知识点：

动态规划解题步骤：

1.状态表示，确定集合与集合的属性

2. 状态计算，状态转移方程

确定基本情况（初始值）