http://acm.hdu.edu.cn/showproblem.php?pid=2159
控制初始化,最后扫描一遍即可。
#include <iostream> #include<cstring> #include<cstdio> #define inf 99999999 using namespace std; int dp[200][200]; int c[200]; int v[200]; int main() { int n,m,k,s; while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) { int i; for(i=1;i<=k;i++) { scanf("%d%d",&v[i],&c[i]); } int j,p; memset(dp,-1,sizeof(dp)); for(i=0;i<=s;i++) dp[0][i]=0; for(i=1;i<=k;i++) { for(j=c[i];j<=m;j++) { for(p=1;p<=s;p++) { if(dp[j-c[i]][p-1]!=-1) dp[j][p]=max(dp[j][p],dp[j-c[i]][p-1]+v[i]); } } } for(i=0;i<=m;i++) if(dp[i][s]>=n) break; if(i>m) printf("-1\n"); else printf("%d\n",m-i); } return 0; }