2133: 信息学奥赛一本通T1269-庆功会

解题思路:优化存储的版本和01背包类似

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 6e3 + 10;
const int M = 5e2 + 10;
int f[M][N],v[M],s[M],w[M];
int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		cin >> v[i] >> w[i] >> s[i];
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			for(int k = 0 ; k <= s[i]; k ++){
			if(j >= k*v[i])
				f[i][j] = max(f[i][j],f[i-1][j - k*v[i]] + k*w[i]);
			}
	cout <<f[n][m];
	return 0;
}