初级动态规划（DP、背包）问题模板

我们知道，在学习算法初期，动规是一个极其折磨人的东西（至少我觉得），为了让我的粉丝数提高新手学习算法时不那么痛苦，我在这篇文章里发布一些初级的背包问题模板（所以不要指望在这里找到多重背包）

#include
using namespace std;
int b[1010][1010],w[1010],v[1010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j 
一维版 
#include
using namespace std;
int w[1010],v[1010],b[1010];
int main()
{
	int m,n;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			b[j]=max(b[j],b[j-w[i]]+v[i]);
		}
	}
	cout< 
布尔型背包 
#include
#include
#include
#include
using namespace std;
int w[1005];
bool b[20005];
int main() 
{
	int n,m;
	cin >> m >> n;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	b[0]=true;
	for (int i=1;i<=n;i++)
	{
		for (int j=m;j>=w[i];j--)
		{
			if (b[j-w[i]]) b[j]=true;
		}
	}
	int j;
	for (j=m;j>=0;j--)
	{
		if (b[j]) break;
	}
	cout< 
完全背包 
#include
using namespace std;
int w[10005],v[10005],b[10005];
int main() 
{
	int n,m;
	cin >> m >> n;
	for (int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=w[i];j<=m;j++)
		{
			b[j]=max(b[j],b[j-w[i]]+v[i]);
		}
	}
	cout< 
---------------------------------------------------------------------------------------------------------------------------------
 
为什么我没有标注释呢？因为我懒时间有限