Dynamic programming -- knapsack problem

f[i][j] Once upon a time i A selection of items , The volume is not greater than j Maximum value of

1. 01 knapsack

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

int f[M];
int dp()
{
	for(int i=0;i<=n;i++)
		for(int j=m;j>=v[i];j--)
			f[j]=max(f[j],f[j-v[i]]+w[i]);
	return f[m];
} 

2. Completely backpack

         Completely backpacking Same layer status to update , Compress to One dimensional positive sequence update

int f[N][M];
int dp()
{
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>=v[i])