http://acm.hdu.edu.cn/showproblem.php?pid=2159
#include<stdio.h>
#include<string.h>
#define max(x,y) x>y?x:y
int main()
{
int ans,n,m,k,s,i,j,a[110],b[110],e,dp[110][110],flag;
while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
{
for(i=1;i<=k;i++)
scanf("%d%d",a+i,b+i);
memset(dp,0,sizeof(dp));
for(e=1;e<=k;e++)
for(i=1;i<=s;i++)
for(j=b[e];j<=m;j++)
dp[i][j]=max(dp[i][j],dp[i-1][j-b[e]]+a[e]);
flag=0;
for(i=1;i<=m;i++)
if(dp[s][i]>=n)
{
flag=1;
ans=i;
break;
}
if(flag)
printf("%d\n",m-ans);
else
printf("-1\n");
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////////////
#include<stdio.h>
#include<string.h>
int n, m, k, s, a, b;
int dp[110], S[110], A[110], B[110], count[110];
int main()
{
int i, j;
while( scanf( "%d%d%d%d",&n, &m, &k, &s ) != EOF )
{
for( i = 1; i <= k; i++ )
{
scanf( "%d%d",&A[i], &B[i] );
}
memset( dp,0,sizeof(dp) );
memset( count,0,sizeof(count) );
int flag = -1;
for( i = 1; i <= k; i++ )
{
for( j = B[i]; j <= m; j++ )
{
if( dp[j] < dp[j-B[i]]+A[i] )
{
dp[j] = dp[j-B[i]]+A[i];
count[j] = count[j-1]+1;
}
}
}
for( i = 1; i <= m; i++ )
{
//printf( "%d %d\n",dp[i],count[i] );
if( dp[i] >= n && count[i] <= s )
{
//printf( "%d---%d %d-----%d\n",dp[i],n,count[i],s );
flag = 1;
printf( "%d\n",m-i );
break;
}
}
if( flag == -1 )
printf( "-1\n" );
}
return 0;
}