题解 | #【模板】完全背包#

完全背包问题,对于第一问,直接再01背包的基础上的内层循环反过来就行,没有过多描述

接下来是对于第二问,我们首先假设前面的有值或者从0转移过来进行转移,这样可以就可以保证这个背包一定是装满的,原理如下:对于开始0处进行转移直接加入就行,假设当前的体积为j,如果vis[j - a[i]]的结果不为0,说明前面的这个数值(j - a[i])一定是可以装满的,我们现在是在装满的基础上进行转移,这样转移后得到的结果一定是装满的情况

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve()
{
	int n,v;cin>>n>>v;
	int f[v+1];
	int vis[v+1];
	vector<int> a(n+1);
	vector<int> b(n+1);
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	memset(f,0,sizeof f);
	memset(vis,0,sizeof vis);
	vis[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i];j<=v;j++)
		{
			f[j]=max(f[j],f[j-a[i]]+b[i]);
			if(vis[j-a[i]])
			{
				if(j-a[i] == 0)
					vis[j] = max(vis[j],b[i]);
				else
				{
					vis[j] = max(vis[j],vis[j-a[i]]+b[i]);
				}
			}
		}
	}
	cout<<f[v]<<'\n';
	cout<<vis[v];
}

signed main()
{
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}