http://poj.org/problem?id=1276
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define For(n) for(int i=1; i<=(n); i++) 6 #define maxn 100010 7 using namespace std; 8 9 int dp[maxn]; 10 struct node 11 { 12 int n; 13 int m; 14 }p[maxn]; 15 int cash,n; 16 17 int main() 18 { 19 while(scanf("%d%d",&cash,&n)!=EOF) 20 { 21 For(n) scanf("%d%d",&p[i].n,&p[i].m); 22 if(n==0||cash==0) {printf("0 ");continue;} 23 int max1=0; 24 memset(dp,0,sizeof(dp)); 25 dp[0]=1; 26 for(int i=1; i<=n; i++) 27 { 28 for(int j=max1; j>=0; j--) 29 { 30 if(dp[j]) 31 { 32 for(int k=1; k<=p[i].n; k++) 33 { 34 int sum=j+k*p[i].m; 35 if(sum>cash) break; 36 dp[sum]=1; 37 max1=max(max1,sum); 38 } 39 } 40 } 41 } 42 printf("%d ",max1); 43 } 44 return 0; 45 }