总结

T1 01背包

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

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

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

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

#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
int n,m;
int v[N];
int f[N][N];
int w[N]; 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];
	}
	for(int i=m;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;
}

T2 完全背包

完全背包和01背包的不同之处在于，物品的数量是​无限的​，值得注意的是，物品数量虽然无限，但是背包容量是有限的，从而推断出每个物品其实是有上限的，我们称之为$x[i]$，即物品$i$最多取$x$个就存不下了。

#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
int n,m;
int v[N];
int f[N][N];
int w[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=0;j<=m;j++)
		{
			for(int x=0;x*v[i]<=j;x++)
			{
				f[i][j]=max(f[i][j],f[i-1][j-x*v[i]]+x*w[i]);
			}
		}
	}
	cout<<f[n][m];
return 0;
}

T3 数字三角形

公式：如果i不等于1时与j不等于1时$f[i][j]=max(f[i-1][j-1],f[i-1[j]+a[i][j]$ 否则 公式：$f[i][j]=a[i][j]$

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[2010][2010];
int f[2010][2010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	f[1][1]=a[1][1];
	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];
			}
		}	
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(f[n][i],ans);
	}
	cout<<ans;
return 0;
}

T4 最长上升子序列I

公式：$f[i]=max(f[i],f[j]+1)$

#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
int a[N],f[N];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=1;
	}
	for(int i=2;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;
}