2023烟台7天编程集训笔记4

//滚动数组代码 
//时间复杂度：O(nm)
#include<bits/stdc++.h>
using namespace std;
int f[maxn][maxn],v[maxn],w[maxn],m,n;//f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获得的最大价值
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];//读入体积和价值
    } 
	for(int i=0;i<=n;i++)
	{
		int p=(i&1);//p 代表 i 的奇偶性
		int q=p^1;//q 代表 i+1 的奇偶性
		memset(f[q],0,sizeof(f[q]));
		for(int j=0;j<=m;j++)
		{
			f[q][j]=max(f[q][j],f[p][j]);//不选
			f[q][h+v[i+1]]=max(f[q][h+v[i+1]],f[p][j]+w[i+1]); 
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++)
	{
		ans=max(ans,f[n&1][i]);
    }
	cout<<ans<<endl;//cout<<f[n][m]<<endl;
}

//有限背包DP代码 
//时间复杂度：O(nm^2)
#include<bits/stdc++.h>
using namespace std;
int f[maxn][maxn],v[maxn],w[maxn],z[maxn],m,n;//f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获得的最大价值
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i]>>z[i];//读入体积和、价值和个数 
    }
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)//要求状态f[i][j] 用别人去求自己 
		{
			for(int k=0;k*v[i]<=j&&k<]z[i];k++)//考虑第 i 种物品选 k 个 
			{
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); 
		    }
	    }
    }
	int ans=0;
	for(int i=0;i<=m;i++)
	{
		ans=max(ans,f[n][i]);
    }
	cout<<ans<<endl;//cout<<f[n][m]<<endl;
}