蓝桥杯算法提高VIP-01背包 （C语言代码）空间优化

解题思路:

注意事项:

参考代码:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cctype>
#include <cstring>
#include <string>
#include <stack> 
#include <algorithm>
#include <functional>
using namespace std;
const int maxv=201;
const int maxw=5001;
int w[maxv], v[maxv], dp[maxw];
int main()
{
	int n, m;
	memset(dp, 0, sizeof(dp));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d%d", &w[i], &v[i]);
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = m; j >= w[i]; --j)
		{
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d\n", dp[m]);
	return 0;
}