Complete knapsack problem from simplicity to ultimate

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int w[N], v[N];
/*int f[N][N];

int main()
{
	int n,m;
	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 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];
	return 0;
}
// The dynamic programming equation is ：f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]);  Curve saves the country .
*/
/*
	 Perform the first optimization ：
	 First ,for(int i=1;i<=n;i++)
		{
			for(int j=0;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]);
				}
			}
		}
	 We extract its dynamic transfer equation ：f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i]) And expand it ：
	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,....) And with f[i][j-v]=max(f[i][j-(k+1)v]+(k+1)w[i] contrast .
	f[i][j-v]=max(        f[i-1][j-v]  ,f[i-1][j-2v]+w ,f[i-1][j-3v]+2w,....)
	 From the above two equations one by one, we can know f[i][j] Each item starting from the second item is related to f[i][j-v]
	 Each item of the corresponds to and is better than f[i][j-v] One more for each item of w, thus it can be seen f[i][j] Starting from the second item 
	 The maximum value is f[i][j-v]+w;
	 thus , The dynamic transfer equation is optimized as :f[i][j]=max(f[i-1][j],f[i][j-v]+w), From the need to enumerate k term 
	 Optimize to just compare two , Optimize the first layer of circulation , At this time, the main code is ：
	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][j-v[i]]+w[i]);
		}
	}
	 At this time, the second round of optimization ： Remove the first dimension :
	for(int i=1;i<=n;i++)
		{
			for(int j=v[i];j<=m;j++)
			{
				f[j]=max(f[j],f[j-v[i]]+w[i]);
			}
		}
	 If with [01 The final code of the backpack ](https://blog.csdn.net/llle_123/article/details/126024930?spm=1001.2014.3001.5501) You will find that they are very similar , But because 01 The backpack is from i-1 layer 
	 To push the first i When we run code in layer, we can't put the number i-1 The data of layer is overwritten in advance, so j From big to small 
	 But the complete knapsack is from the first i Layer launched i Layers need to be updated in advance , so j From small to large ;

*/
int f[N];
int main() {
	int n, m;
	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 = v[i]; j <= m; j++) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[m];
	return 0;
}