模拟退火

#include<bits/stdc++.h>
using namespace std;
#define db double
#define int long long
const int N=110;
int n,X,Y,ans;
struct nd{int x,y;}p[N];
int calc()
{
	int s1=0,s2=0;
	for(int i=1;i<=n;i++)
	{
		s1+=p[i].x;s2+=p[i].y;
		if(s1>X||s2>Y)
		{
			ans=max(ans,i);
			return i;
		}
	}
	ans=n;return n;
}
void SA()
{
	for(db t=1e5;t>=1e-7;t*=0.998)
	{
		int x=calc();
		int u=rand()%n+1,v=rand()%n+1;
		swap(p[u],p[v]);
		int y=calc();
		if(y>x)continue;
		if(db(exp(db(y-x)/t))>db(rand())/RAND_MAX)
			continue;
		swap(p[u],p[v]);
	}
}
signed main()
{
	srand(time(0));
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>X>>Y;
	for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
	sort(p+1,p+n+1,[](nd n1,nd n2){return n1.x<n2.x;});
	for(int i=1;i<=300;i++)SA();
	cout<<ans;return 0;
}

三维DP,跑得较慢

定义 $f(i,j,k)$ 为前 $i$ 道菜中吃 $j$ 道且甜度为 $k$ 时咸度的最小值。

using namespace std;
const int N=100,M=1e4+10;
int a[N],b[N],f[N][N][M];
int main()
{
	int n,x,y;scanf("%d%d%d",&n ,&x,&y);
	for(int i=1;i<=n;++i)scanf("%d%d",&a[i],&b[i]);
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<=n;++i)f[i][0][0]=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)
		for(int k=0;k<=x;k++)
		{
			if(k>=a[i])f[i][j][k]=f[i-1][j-1][k-a[i]]+b[i];
			f[i][j][k]=min(f[i][j][k],f[i-1][j][k]);
		}
	for(int i=n;i>=0;i--)for(int j=0;j<=x;j++)
		if(f[n][i][j]<=y)
		{
			printf("%d\n",min(i+1,n));
			return 0;
		}
	return 0;
}

二维DP

令 $f_{i,j}$ 为甜度为 $i$，已经吃了 $j$ 道菜的甜度最小值。先枚举考虑到第 $i$ 道菜，再从大到小枚举累计的甜度 $j$，最后枚举吃了的菜的数量 $k$，转移方程为 $f_{j,k} = \min \{ f_{j−a_i,k-1} + b_i \}$

#include<bits/stdc++.h>
using namespace std;
const int N=100,M=1e4+10;
int ans,a[N],b[N],f[N][M];
int main()
{
	int n,x,y;scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	memset(f,0x3f,sizeof(f));
	for(int i=0;i<=x;i++)f[0][i]=0;
	for(int i=1;i<=n;i++)for(int j=x;j>=1;j--)
		for(int k=1;k<=n;k++)if(j>=a[i]&&f[k-1][j-a[i]]+b[i]<=y)
		{
			f[k][j]=min(f[k][j],f[k-1][j-a[i]]+b[i]);
			ans=max(ans,k);
		}
	if(ans<n)ans++;
	printf("%d\n",ans);
	return 0;
}