学步园

二维完全背包

#include<stdio.h>
#include<string.h>
#define inf 0x3fffffff
int dp[101][101];
int main()
{
	int i,j,n,m,k,s,v[101],w[101],p;
	while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
	{
		memset(dp,0,sizeof(dp));
		for(i=0;i<k;i++)
			scanf("%d%d",&w[i],&v[i]);
		for(i=0;i<k;i++)
		{
			for(j=1;j<=s;j++)
				for(p=v[i];p<=m;p++)
				{
					if(dp[j][p]<dp[j-1][p-v[i]]+w[i])
					   dp[j][p]=dp[j-1][p-v[i]]+w[i];
				}
		}if(dp[s][m]<n){puts("-1");continue;}
		int ma=inf;
		for(i=1;i<=s;i++)
			for(j=1;j<=m;j++)
				if(ma>j&&dp[i][j]>=n)
					ma=j;
					printf("%d\n",m-ma);
	}
	return 0;
}